Lili Marlene started as a poem, written by Hans Leip, a 22 year old German soldier, fighting in the First World War; he published it, with other poems in 1937. It was originally quite explicitly anti-war and was set to music by Norbert Schultze, who, because of the sentiment, had difficulty getting it published in Germany. It was recorded by Lale Anderson, a popular singer of the time, but didn't sell and then was banned, as anti-patriotic, by the Nazis.
In 1941, it was one of the few records at the German radio station in Belgrade which survived shelling and, despite being banned, was played by the station, becoming a huge hit with the German forces in North Africa. It also took off with the British and American troops, who also picked up the broadcast.
A group of British soldiers, singing the song on leave in London were taken to task by Jimmy Phillips, a music publisher, for singing in German and challenged him to come up with an English version, which he did, with one Tommy Connor. Their version lost Leip's original anti-war sentiment and made it a straight up yearning for lost love; several artists have recorded it, including Marlene Dietrich (in English and German), Vera Lynn, Bing Crosby and Spanish Disco ensemble Ole Ole.
When the original recording artist, Lale Andersen, was asked in 1972 if she could explain the popularity of Lili Marlene, she replied, "Can the wind explain why it became a storm?" Other versions include a wonderful interpretation from June Tabor, with a great introduction about the song's history, Kid Creole and the Coconuts, and, um , 'Slovenian Post-Punk Darkwave'.