История «Смуглянки» началась с того, что в 1940 году руководство Ансамбля песни и пляски Киевского военного округа предложило композитору Анатолию Новикову написать песенную сюиту о борьбе молдавских партизан времён Гражданской войны. Композитор заказ выполнил. Песня «Смуглянка», написанная на стихи Якова Шведова, стала заключительной в ряду семи песен, входящих в сюиту. Однако шесть песен ансамбль принял к исполнению, а седьмую, «Смуглянку», почему-то забраковал. 

Когда началась Великая Отечественная война, Новиков, всё же считавший «Смуглянку» своей творческой удачей, предложил песню редакторам Всесоюзного радио для исполнения в эфире. Их ответ был для композитора неожиданным: «Ну что за песню вы нам предлагаете? Про любовь, свидание, расставание с какой-то смуглянкой-молдаванкой! Сейчас настало такое тяжёлое для страны время, такая война!... Вы же автор популярных патриотических песен – вот и пишите такие!». 

Обескураженный столь категоричным ответом, Анатолий Григорьевич запрятал ноты песни поглубже в свой творческий архив, а вскоре из-за досадного недоразумения партитура всей сюиты, включая «Смуглянку», и вовсе была утеряна. Казалось бы, песня, навсегда канула в небытие, так и не дойдя до слушателя. Но неожиданно случилось чудо. 

«Как-то в 1944 году мне позвонил художественный руководитель Краснознамённого ансамбля Александров, – рассказывал композитор, – и спросил, нет ли новых песен». Новиков вспомнил об утраченной «Смуглянке». Какие-то фрагменты мелодии он смог восстановить по оставшимся черновикам-наброскам, что-то сочинил заново. А вот воссоздать текст песни оказалось сложнее: автор слов Яков Шведов в это время находился на фронте. 

«Пришло письмо с нарочным от Новикова, – рассказывает дочь Шведова Наталья Гончарова. – Он сообщал, что переписал музыку, и нужно было «вклинить» в партитуру новые слова – чтобы они более мягко, что ли, звучали. Люди устали – от грязи, от крови, и все знали – война вот-вот закончится, уже наши войска перешли границу Советского Союза. Хотелось раскрепоститься, отдохнуть душой. И вот тут «Смуглянка» очень хорошо легла». Александров был в восторге. 

Начались репетиции, но со «Смуглянкой» опять возникли сложности. Песня была написана в одной тональности – ля минор, тенор начинал, а затем вступал баритон, и они вдвоём должны были петь некоторое время. Но из дуэта ничего не получалось, почему-то был полный разлад. «И тут выручил солист Николай Устинов, – рассказывал композитор Новиков. – Он спросил у Александрова: может быть, запевать не тенору, а баритону? «Только, – говорит, – пониже немного возьмите тональность»... Музыканты согласились: «Так сыграть можем». Александров задал темп, заиграли, и Устинов запел. Потом к нему присоединился тенор, подхватил хор, – и всё встало на место. Находку зафиксировали. «У нас сегодня концерт в зале Чайковского, – говорит Александров, – давайте её споём». Всю песню Анатолий Новиков прослушал, как в тумане, и очнулся, лишь когда раздались крики «браво» и «бис». «В тот момент я понял, что песня удалась», – говорил композитор. 

Веселая, бойкая песня о любви партизана и смуглянки-молдаванки стала собирательным образом любви молодых людей, объединённых общей борьбой с немецкими захватчиками. Неудивительно, что она тут же всем полюбилась и стала передаваться из уст в уста. Так её впервые услышал 16-летний Леонид Быков – в поезде, от двух фронтовых офицеров, ездивших в Молдавию на могилы своих однополчан. Мотив настолько запал ему в душу, что когда спустя 3 десятилетия уже известный актёр и режиссёр Леонид Быков начал работу над картиной «В бой идут одни старики», он уже точно знал, какая мелодия станет в нём главной. И именно Быков дал «Смуглянке» третье счастливое рождение.