It premiered in 2010 at London's Menier Chocolate Factory in a production co-directed by Hal Prince and Susan Stroman.

In an interview, Hal Prince said that the musical would "center on a Middle Eastern ruler who travels to Vienna in search of romantic 'inspiration,' and the machinations that occur when he demands a rendezvous with a noblewoman who turns out to be the empress of Austria."

[1] Early readings featured John Cullum, Mandy Patinkin, Shuler Hensley, Judy Kaye, Emily Skinner, Rebecca Luker and Kate Baldwin.

[3] The cast featured John McMartin as the Shah of Persia, Mandy Patinkin as a Eunuch, Shuler Hensley as the Baron, Judy Kaye as Frau Matzner and Kate Baldwin as Mizzi.

"[5] The British Theatre Guide reviewer noted that "'Paradise Found' is a serviceable light comedy musical but with the talents available, many visitors might have hoped for an evening a little closer to Paradise.