"To jump out of the frying pan into the fire" (and variants thereof) is perhaps the most widespread figure of speech in the Western world, very similar variants are shared by: Greek, "out of the smoke into the flame"; Italian and Portuguese, "to fall from the frying pan into the coals"); and French, from which the English may be a direct translation: "to leap from the frying pan into the fire" (tomber de la poĂȘle dans le feu). The sense of the term is also universal throughout the languages: to escape one predicament only to find yourself in another one, as bad or worse.

The English form of this phrase is traceable to a religious argument that arose between William Tyndale, translator of the Bible into English, and Sir Thomas More. The argument started in 1528 upon the publication of a paper by More, A Dialoge concerning Heresyes. This elicited a treatise from Tyndale in 1530, An Answere unto Sir Thomas Mores Dialoge, and this in turn brought forth from More, two years later, The Confutacyon of Tyndales Answere, wherein More brings in our expression, saying that his opponent "featly conuayed himself out of the frying panne fayre into the fyre."

The most fame this phrase has attained in literature is probably its use as a chapter title in J.R.R. Tolkien's "The Hobbit." Thanks to Pseudo_Intellectual for reminding me about this.