According to Paul, there are two covenants. One he allegorically compares to Hagar and bondage, while the other to Sarah and freedom. This is the difference between the "covenant of works" and "the covenant of grace". All covenants between God and men in the Bible fall within these two basic camps.
Which things are an allegory: for these are the two covenants; the one from the mount Sinai, which gendereth to bondage, which is Agar. For this Agar is mount Sinai in Arabia, and answereth to Jerusalem which now is, and is in bondage with her children. But Jerusalem which is above is free, which is the mother of us all. (Gal 4:24-26).
First, what is the covenant from Mount Sinai that results in bondage? (Gal 4:24) This is the old covenant, the covenant of works, given by God to the Israelites at Sinai. The terms of which was Obey and live (Ezekiel 20:11, Leviticus 18:5), Disobey and be cursed (Deuteronomy 27:26, Gal 3:10). In other words, this covenant expected men to obey from their own righteousness, possible before sin, but impossible post sin, and therefore referred to as "bondage". Paul goes as far as to call it a "ministration of death" (2 Cor 3:7), the law written externally on tables of stone (2 Cor 3:7).
Then what of the second covenant, which is referred to as freedom (Gal 4:26)? This is the new covenant, the covenant of grace, which is establish upon "better promises" (Hebrew 8:6) -- the promise of forgiveness of sins and of the grace of God, and obedience to God through the process of sanctification, the same law written instead upon fleshy tables of the heart (2 Cor 3:3, Hebrew 10:16).
So far so good, but there is a further layer to be grasped:
Since "the covenant of grace" is the promise of forgiveness of sin and grace, this covenant actually existed prior to Jesus as the Abrahamic covenant, for it had existed as a promise. Paul explains:
Now to Abraham and his seed were the promises made. He saith not, And to seeds, as of many; but as of one, And to thy seed, which is Christ. And this I say, that the covenant, that was confirmed before of God in Christ, the law, which was four hundred and thirty years after, cannot disannul, that it should make the promise of none effect. (Gal 3:16-18).
And if you are Christ’s, then you are Abraham’s seed, and heirs according to the promise. (Gal 3:29)
For what saith the scripture? Abraham believed God, and it was counted unto him for righteousness. (Roman 4:3)
But if the new covenant first existed as the Abrahamic covenant, why is it called "new" while the other one "old" and "first"? This is because the new testament has existed as a promise at first, and was ratified with Jesus' own blood at the cross (Hebrews 9:12), while the old covenant was ratified first with the "blood of calves and goats" at Sinai (Hebrews 9:18-20)
For where a testament is, there must also of necessity be the death of the testator. For a testament is of force after men are dead: otherwise it is of no strength at all while the testator liveth. (Hebrew 9:16-17).
Therefore, although Abraham was justified by faith, if Christ never died, the promise would have been of no effect. Finally, since the Abrahamic covenant is called "the everlasting covenant" (Genesis 17:7), the covenant of grace is the everlasting covenant. It was first hinted to Adam after he sinned (Genesis 3:15), and is really the plan of salvation, put in place before the foundation of the world (Rev 3:18).
A fuller expounding of this topic is in Patriarchs and Prophets, pg. 370-372
