The same expression or one closely allied to it is common to many languages.
In the second century the Greek equivalent was “out of the smoke into the flame”; the Italian and Portuguese, “to fall from the frying pan into the coals”; the Gaelic, “out of the cauldron into the fire,” and the French, from which the English may be a translation, “to leap from the frying pan into the fire (comber tie la pale dans k feu).”
The sense of the expression has always been to escape one evil predicament by leaping into another just as bad or worse.
English usage is traceable to a religious argument that arose between William Tyndale, translator of the Bible into English, and Sir Thomas More, best remembered now as the author of Utopia.
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 adversary “featly conuayed himself out of the frying panne fayre into the fyre.”
It is a little grim to recall that Tyndale was publicly strangled and burned as a heretic in 1536, but that More was not alive to rejoice, for he, a year earlier, had been hung, through perjured testimony, as a traitor because he would not approve the bigamous marriage of Henry VIII to Anne Boleyn.