I get this question with some frequency, usually around Reformation Day. Here is a preliminary answer:
The ideas were present from the earliest stage of the Reformation, but the actual phrases developed over time. The earliest phrases were sola gratia (by grace alone) and sola fide and sola scriptura. These are easily found in early 16th century protestant texts.
Sola Gratia
Andreas Bodenstein von Karlstadt, before he radicalized, used the expression sola gratia repeatedly in his 1519 disputation.
Martin Bucer used it in his 1536 commentary on the Gospels and again in a 1545 tract. The Italian Reformer, Peter Martyr Vermiligi used it in his 1558 lectures on Romans. Wolfgang Musculus used it in his lectures on Galatians and Ephesians (1561). Caspar Olevianus used it in his lectures on Romans (1579).
Calvin defended the notion and used the phrase, in Institutes 2.3.11. He was arguing against the Roman notion of “cooperating grace” in justification. See also 3.11.5; 3.14.5; 3.24.12.
Sola Fide
Luther used it famously in his translation of Galatians 3. He also used it in his lectures on Galatians. (His defense of inserting “allein” is below). In 1521, Melanchthon used it in his Loci Communes (Common Places, his systematics text) exactly as we do today.
Karlstadt used sola fide also in 1519 in his disputation. The significance of this is that he was certainly reflecting, at this point, what Luther and Melanchthon were saying. The phrase is also found in the work of Francois Lambert (1524); Johannes Oecolampadius (1524, 1534), Martin Bucer (1527, 1534, 1536, 1545), Heinrich Bullinger (1534, 1557), Peter Martyr Vermigli (1549) and in Calvin (Institutes 3.3.1; 3.11.1; 1.11.19; 3.14.17 etc). It is also found, of course, in the Augsburg Confession Art. 6.
The Latin text of the Heidelberg Catechism (1563) uses the expression sola fide in Q. 60 on justification.
Sola Scriptura
Sola Scriptura is certainly a sixteenth-century phrase. The expression itself occurs among the Reformed as early as 1526 and Bucer used it in 1536. Calvin used it in Institutes 3.17.8.
Solo Christo and Soli Deo Gloria
I do not know the original dates for the phrases, solo Christo (i.e. “in Christ alone”) and soli Deo gloria (to God alone be the glory) but my guess is that their origins are probably a little later. Jim Renihan suggested that they might be traceable to Merle D’Aubigne. That seems like a good possibility but one which I’ve not investigated yet.