Christianity has long been debating the relationship between God's will and human wills in our salvation, probably all the way back to the very early church. The debate between Reformed and Arminian Protestants is only one part of this broader debate.
Augustine vs the Pelagians
Pelagianism is a position, now considered heretical by all major Christian groups, that humans are not corrupted by original sin, and we have the ability to freely will to act righteously and achieve human perfection without divine grace. This position was opposed by Augustine who taught that we are corrupted by original sin, and unable to choose good, and that we depend on God's grace for salvation. The Reformers saw themselves as being part of the Augustinian school of theology, and that their teachings were largely a reform to Augustine's teachings, and not innovative. Even people such as Augustine changed their views over their life: he originally taught that predestination was based on God's foreknowledge of whether an individual would believe, and was a reward for human assent, but shifted to saying that it is God's grace that causes faith, the position taken up in Reformed Theology.
The 'Semi-Pelagians' (a debated term, but I use it now because it's the best known of the many alternatives) agreed that Pelagianism was heresy, but then taught a position between the two which many Augustinians thought was also wrong. Semi-Pelagianism says that the beginning of faith is an act of free will, but continuing growth in faith is a work of God. Within both Protestantism and Catholicism there have been debates where one side has called the other 'semi-Pelagian', so it's not a very clear term.
After Augustine there were a range of views. Cassian taught that human nature is fallen and depraved, but not totally, and that both God's will and the free human will work in repentance. Aquinas taught that God predestines people based solely on his own goodness, but that people have free will, and cause and are responsible for their sins. William of Ockham however said that God does not cause human choices, and that predestination is only God's foreknowledge, without God thereby being bound by human wills.
So you see that by the time of the Reformation there had already been over a thousand years of debate on this topic. Within Western Catholicism there were a range of views about original sin, election and predestination, and human free will. Reformed Calvinists and Arminians both stand firmly opposed to Pelaginism and would also say they oppose semi-Pelagianism (though Arminians are sometimes accused of it). Calvinists see themselves as standing with Augustine and Aquinas in their teachings on predestination, while Arminians can say that they have the support of early-Augustine, Cassian, Ockham, and others. Catholic views continued to develop too: Molinism, named after the 16th century Jesuit Luis de Molina, is a more developed form of the predestination based on foreknowledge view, where God knows all counterfactuals and all possible worlds, and chooses which world to create such that all he wills comes to pass, while all humans freely choose every decision. There are many Protestant Molinists now, probably from both Reformed and Arminian backgrounds.
But it is also not as if the debates between Protestants are merely playing musical chairs on the positions created by earlier generations. Like the Catholics, Reformed Theology has continued to develop its view of free will: humans have true free wills to live in accordance with our natures; unfortunately our natures are so bent towards sin that we cannot will to convert ourselves. This view of free will, that it means the freedom to be consistent with who we are, may be new for Reformed Theology, or maybe there are precursors I'm not aware of. Another attempt to rationalise all the Biblical data is the corporate election view which says that God's election is of the church as a whole, rather than individuals. And of course theologians of Western Christianity (Catholicism and Protestantism) continue to engage with the theologies of Eastern Christianity and the non-Trinitarian Restorationist movements.
Arminians and Lutherans agree with the Reformed that without God's gracious intervention no one could ever come to faith (contra the Pelagians). If I were to try to boil down the debate between Arminians and Reformed, it would concern the nature of God's prevenient grace: does it free us from the bounds of sin to let us freely choose to repent or not, or does it transform and regenerate us, giving new life to our wills so that we will invariably grow the fruit of faith?