В 1938 году Шульце написал новую мелодию, с которой “Лили Марлен” и вошла в историю. Лале Андерсен записала на пластинку второй вариант песни, но и он поначалу фурора не произвел. Было продано только 700 экземпляров пластинки.
Лале исполняла “Лили Марлен” как нежную, лиричную песенку. В 1941 году Норберт Шульце решил, что петь ее надо по-другому. Это было время первых побед во Второй мировой войне, когда наиболее востребованными стали военные марши. К тому же министр пропаганды Третьего рейха Йозеф Геббельс отдавал предпочтение маршам, а лирика его интересовала мало. Шульце сделал новую аранжировку — “Лили Марлен” получила ритм марша.
Некоторые журналисты пишут, что именно Геббельс посоветовал Шульце переделать мелодию. На самом деле, едва министр пропаганды услышал “Лили Марлен”, она сразу была запрещена из-за своего содержания. Геббельс называл песню слащавой дешевкой с душком мертвечины (вспомним ее окончание). Даже в период популярности “Лили Марлен” он выступал против исполнения этой песни, считая, что она не соответствует идеологии империи-победительницы как упадническая, “подрывает моральный дух солдат”. Но и всесильный Геббельс ничего не мог поделать — песня полюбилась простым солдатам, вспоминавшим в окопах о своих девушках и верившим, что те будут их ждать. К тому же она понравилась Гитлеру, который не отличался изысканным вкусом и был человеком более неотесанным, чем его министр пропаганды. “Лили Марлен” завоевала народную любовь, а Лале Андерсен стала звездой.
Мировая слава началась с того, что “Лили Марлен” в исполнении Андерсен прозвучала в эфире радио “Белград” (“Soldatensender Belgrad”). Эта фронтовая радиостанция была установлена на территории оккупированной Югославии. Ее слушателями были солдаты, расквартированные на Балканах, и африканский корпус “Лбиса пустыни” генерал-фельдмаршала Роммеля, воевавший в Ливии. У директора Белградского радио, лейтенанта Карла Хайнца Райнтгена (Karl Heinz Reintgen), в Северной Африке служил друг, который любил “Лили Марлен”. И Райнтген решил для него поставить пластинку с записью Лале Андерсен. Впервые она прозвучала по радио 18 августа 1941 года. “Лили Марлен” понравилась самому фельдмаршалу, он попросил, чтобы она исполнялась чаще. Вскоре “Белград” начал транслировать ее каждый вечер в 21.55, незадолго до сигнала “отбой”, после передачи, в которой зачитывали письма с фронта. “Лили Марлен” стала позывными радиостанции.