This page has quotes in which the earliest Christians reference the New Covenant as the New Law. Hebrews 7:12 uses similar terminology:
He has revealed to us by all the prophets that he needs neither sacrifices, nor burnt offerings, nor oblations. he says, "'What is the multitude of your sacrifices to me,' says the Lord? 'I am full of burnt offerings and do not want the fat of lambs and the blood of bulls and goats—not when you come to appear before me. For who has required these things from you? Don't tread on my courts anymore, not even if you bring fine flour with you. Incense is a useless abomination to me, and I cannot endure your new moons and Sabbaths'" [Isa. 1:11-14]. He has therefore abolished these things so that the new law of our Lord Jesus Christ, which is without the yoke of necessity, might have a human oblation.* (Letter of Barnabas 2)
*The Latin version of the Letter of Barnabas reads as I have rendered it. The Greek version reads, "... might not have a man-made oblation." The editors of The Ante-Nicene Fathers suggest the Latin is preferable and that the meaning is that we offer ourselves rather than animals.
We do not trust through Moses or through the law ... for I have read there shall be a final law and a covenant, the chiefest of all, which it is now incumbent on all me to observe, as many as are seeking after the inheritance of God. For the Law promulgated on Horeb is now old, and belongs to you [Jews] alone, but this is for all universally. Now, law placed against law has abrogated that which is before it, and a covenant which comes after in like manner has put an end to the previous one. An eternal and final law—namely, Christ—has been given to us, and the covenant is trustworthy. After it there shall be no law, no commandment, no ordinance. (Dialogue with Trypho, a Jew 11)
If, therefore, God proclaimed a new covenant which was to be instituted ... we see and are persuaded that men approach God, leaving their idols and other unrighteousness, through the name of the one who was crucified, Jesus Christ. They stand by their confession even to death and maintain godliness. In addition, by the works and by the miracles which attended him, it is possible for everyone to understand that [Jesus] is the New Law, the New Covenant, and the expectation of those of every people who wait for the good things of God. (Dialogue with Trypho, a Jew 11)
The Lawgiver is present, yet you do not see him. To the poor the Gospel is preached. The blind see, yet you do not understand. You now have need of a second circumcision, although you take great pride in the flesh.
The New Law requires you to keep perpetual Sabbath, and you, because you are idle for one day, suppose you are godly, not discerning why this has been commanded to you. If you eat unleavened bread, you say the will of God has been fulfilled. The Lord our God does not take pleasure in such observances. If there is any perjured person or a thief among you, let him cease to be so; if any adulterer, let him repent. Then he has kept the sweet and true Sabbaths of God. If anyone has impure hands, let him wash and be pure. (Dialogue with Trypho, a Jew 12)
After the seven days of eating unleavened bread, God commanded [the Israelites] to mingle new leaven; that is, the performance of other works, and not the imitation of the old and evil works. Because this is what this new Lawgiver demands of you, I shall again refer to the words which have been quoted by me ... They are related by Isaiah to the following effect: "Listen to me, and your soul shall live, and I will make an everlasting covenant with you ... Behold, I have given him as a witness to the people, a leader and commander to the nations. ... Seek God, and when you find him, call on him, as long as he is near you. Let the wicked forsake his ways and the unrighteous man his thoughts, and let him return to the Lord. He will obtain mercy, because he will abundantly pardon your sins" [Isa. 55:3ff]. (Dialogue with Trypho, a Jew 14)
Wash therefore, and be clean. Put away iniquity from your souls. God bids you to be washed in this laver and be circumcised with true circumcision. For we, too, would observe the fleshly circumcision and the Sabbaths—and, in short, all the feasts—if we did not know why they were imposed upon you: because of your transgressions and the hardness of your hearts. For if we patiently endure everything contrived against us by wicked men and demons, so that even amid cruelties unutterable, death, and torments, we pray for mercy for those who inflict such things upon us ... even as the new Lawgiver commanded us, then how is it, Trypho, that we would not observe those rites that do not harm us? I speak of fleshly circumcision, Sabbaths, and feasts. (Dialogue with Trypho, a Jew 18)
You [Jews] deceive yourselves by ambiguous forms of speech. For where it is said, "The Law of the Lord is perfect," you do not understand it of the law which was to come after Moses, but of the law which was given by Moses, although God declared that he would establish a new law and a new covenant [cf. Jer. 31:31-34]. (Dialogue with Trypho, a Jew 34)