The song was originally composed by the Greek composer Manos Hadjidakis and recorded in Greek by Tzeni Karezi for the soundtrack of the film To nisi ton genneon (The Island of the Brave); the original song in Greek is titled "Μην τον ρωτάς τον ουρανό" ("Min ton rotas ton ourano", translation: "Don't ask the sky").
Later, a new version of the song with English lyrics was produced by Owen Bradley and appeared as the title track on one of Lee's albums.
In 1960, the Greek film Never on Sunday was released to considerable acclaim, earning multiple Academy Award nominations in the US.
A melody that appeared in both Never on Sunday and The Island of the Brave was sent to Lee's management as a tune to be considered for the singer to record, and after being translated into English by Arthur Altman, became "All Alone Am I".
[1] The B-side to the single, "Save All Your Lovin' For Me", reached number 53 on the US pop chart.