Predestination, on the other hand, is a related concept but distinct and has to do with theological anthropology, not human history at large. The doctrine approaches the question of human salvation in relation to two tricky concerns — the absolute grace of God that justifies the human person and human responsibility.
The pre-Augustinian position which is held by the Eastern churches to this day as well as some Protestants, and which was maintained by many of the ecclesiastics in southern Gaul against Augustinianism (the Gallic Chronicle of 452 refers to ‘the heresy of the predestinationists’ while also opposing Pelagianism) draws upon a specific reading of Romans 8:28-30:
Although he is not a Church Father, my preferred explication of these verses from a non-Predestinationist view (‘Arminian’ in modern terms) is John Wesley, who, like Origen and Hilary of Poitiers and Ambrosiaster as well as the young Augustine before him, sees God’s foreknowledge as being the prerequisite to the predestination. God in his infinite wisdom sees all of human history, and he sees those who will have a natural turning towards Him; to these who are already inclined to love Him and put faith in Him, He gives His grace to help them turn more fully to him, thus predestining them for salvation due to His divine omniscience. (See here: http://www.umcmission.org/Find-Resources/John-Wesley-Sermons/Sermon-58-On-Predestination)
John Cassian, the monastic founder in Marseille, also addressed this issue ca. 435 in the 13th book of his Conferences. He sets out a vision of predestination that says that all humans have enough of the original image of God in them (fr. Gen 1) that they are able to turn towards God, yet God does not withhold His grace from them, but rather provides this grace to help those who have started to turn to turn all the way. In the early modern period, this view was wrongly termed ‘semi-Pelagian’, and others who share it with Cassian are Faustus of Riez (who is a shockingly insistent rigorist when it comes to post-baptismal sin; some excerpts of Faustus’ letters are in an appendix to Ralph W Mathisen’s TTH book Ruricius of Limoges and Friends) and Vincent of Lérins (Commonitorium).
Boniface Ramsay, in his commentary to the Ancient Christian Writers translation of the Conferences calls Cassian’s view ‘semi-Augustinian’, interestingly enough. These people are often called Massilian because of their southern Gallic origins; they resist both extreme Augustinianism and Pelagianism. I have sympathies with their enterprise to do justice both to God’s grace and human responsibility/freedom. I’ve blogged on Cassian and this issue before.
Augustine’s view started to shift, largely through confrontation with Pelagians such as Julian of Eclanum, while he was Bishop of Hippo. There is a fully-fleshed vision of Augustinian predestination that would be pressed after his death by supporters such as Prosper of Aquitaine and enshrined at the Council of Orange in 529 (albeit local councils do not have universal jurisdiction; the Council of Orange is therefore not binding for the western Church in terms of developed Canon Law vs. certain early modern Protestants; the canons are here: http://www.ewtn.com/library/COUNCILS/ORANGE.htm). This is the version most people think when they hear ‘Augustine. Predestination.’ The teaching is that the human will is fallen and cannot of itself turn towards God, therefore grace is necessary for every step of human salvation, including good deeds.
Pelagius is somewhat in fashion these days; he was a presbyter in Rome who, upon hearing a line of Augustine’s, was a bit worried that people would slip in moral laxity if they simply relied on grace with no works for their salvation. While the current scholarly consensus is that he was not an exponent of the heresy that bears his name, Pelagianism, to put it crudely, is the teaching that the human will is not actually fallen, and that we all do bad stuff simply because of bad examples. If we had truer knowledge, we would be able to will properly and thus live properly. Since God’s grace would nullify free will, Pelagianism teaches that we do not receive any and that it is up to our own work to become holy and attain to salvation. The best description of Pelagianism I have read is in A M C Casiday, Tradition and Theology in St John Cassian.
Over time, and through controversy both with Pelagians and the Massilians, Augustine’s view on predestination was moderated, as seen in his tract On Grace and Freewill (available in the Ancient Christian Writers translation series from Paulist Press). This latter piece argues almost for both positions — humans are responsible, yet we rely entirely on God’s grace. Augustine will still lean more towards grace alone, but he makes room for compromise with people such as Cassian.
In response to rumours of Pelagians at large in northern Italy, Leo the Great sent his first, second, and eighteenth letters, saying:
And since they pretend to reject and put aside all their definitions to help them sneak in, they seize on this with all their art of deceit, unless they are understood, that the grace of God is felt to be given according to the merits of the recipients. Which, of course—unless it were given gratis—is not grace, but payment and recompense for merits: as the blessed Apostle says, ‘You were saved by grace through faith, and this is not from yourselves but it is the gift of God, not from works, lest perhaps some be exalted. For we are his handiwork, created in Christ Jesus for good works, which God has prepared that we may walk in them.’ And so every bestowal of good works is a divine preparation: because no one is justified by virtue before grace, which is the beginning of justice, the fount of good things, and the origin of merits for one and all. But by these men, therefore, it is said to be anticipated by that innate industry so that which was clear by its own zeal before grace, seems not harmed by any wound of original sin; and it is false which Truth said, ‘For the Son of Man came to seek out and to save that which had perished.’ -Ep. 1.3, my trans.
 Ephesians 2:8-10.
 Luke 19:10.
For information, the official stance of the Anglicans on the issue is:
Predestination to Life is the everlasting purpose of God, whereby (before the foundations of the world were laid) he hath constantly decreed by his counsel secret to us, to deliver from curse and damnation those whom he hath chosen in Christ out of mankind, and to bring them by Christ to everlasting salvation, as vessels made to honour. Wherefore, they which be endued with so excellent a benefit of God be called according to God’s purpose by his Spirit working in due season: they through Grace obey the calling: they be justified freely: they be made sons of God by adoption: they be made like the image of his only-begotten Son Jesus Christ: they walk religiously in good works, and at length, by God’s mercy, they attain to everlasting felicity.
As the godly consideration of Predestination, and our Election in Christ, is full of sweet, pleasant, and unspeakable comfort to godly persons, and such as feel in themselves the working of the Spirit of Christ, mortifying the works of the flesh, and their earthly members, and drawing up their mind to high and heavenly things, as well because it doth greatly establish and confirm their faith of eternal Salvation to be enjoyed through Christ, as because it doth fervently kindle their love towards God: So, for curious and carnal persons, lacking the Spirit of Christ, to have continually before their eyes the sentence of God’s Predestination, is a most dangerous downfal, whereby the Devil doth thrust them either into desperation, or into wretchlessness of most unclean living, no less perilous than desperation.
Furthermore, we must receive God’s promises in such wise, as they be generally set forth to us in holy Scripture: and, in our doings, that Will of God is to be followed, which we have expressly declared unto us in the Word of God. (Article of Religion XVII)
To close, if any Pelagians happen upon this blog, I am open to clear explications of the Pelagian position. However, I will not suffer ad hominem attacks on myself, my intellect, or St Augustine. If you troll, your comments will be removed.