But beyond all this, there was a debt owing which must needs be paid; for, as I said before, all men were due to die. Here, then, is the second reason why the Word dwelt among us, namely that having proved His Godhead by His works, He might offer the sacrifice on behalf of all, surrendering His own temple to death in place of all, to settle man’s account with death and free him from the primal transgression. (De Incarnatione IV.20)
Death there had to be, and death for all, so that the due of all might be paid. Wherefore, the Word, as I said, being Himself incapable of death, assumed a mortal body, that He might offer it as His own in place of all, and suffering for the sake of all through His union with it, “might bring to nought him that had the power of death, that is, the devil, and might deliver them who all their lifetime were enslaved by fear of death.” (De Incarnatione IV.20)
Have no fear, then. Now that the common Saviour of all has died on our behalf, we who believe in Christ no longer die, as men died aforetime, in fulfilment of the threat of the law. (De. Incar. IV.21)
He had come to bear the curse that lay on us; and how could He “become a curse” otherwise than by accepting the accursed death? And that death is the cross, for it is written “Cursed is every one that hangeth on a tree.” (De. Incar. IV.25)
For another important early church father on substitutionary atonement, have a look at this post from Martin Downes giving a few excerpts from Augustine.