В 1940 году поэт-песенник Яков Шведов и композитор Анатолий Новиков получили от ансамбля Киевского особого военного округа заказ на сюиту, посвященную Григорию Котовскому. Одной из семи композиций стала основанная на бессарабском фольклоре песня «Смуглянка» о девушке из партизанского отряда. Но сюита так и была исполнена. В 1943 году в станице Тимашевской, под Краснодаром, проходили съемки киноленты «Война в воздухе» и песню «Смуглянка» пробовали в съемках фильма, но затем она вновь была забыта и оказалась «на полке» до 1944 года. Более того, ее судьба могла сложиться печально, ведь затерялось даже переложение для фортепиано. К счастью, у композитора сохранились черновые наброски произведения. И когда к Новикову за новыми песнями для очередной праздничной концертной программы обратился Александр Васильевич Александров, Анатолий Григорьевич доработал песню, связался с Яковом Шведовым, который в тот момент служил на 2-м Украинском фронте, чтобы тот немного переделал текст. Несмотря на войну и сложности с почтой, изменённый текст быстро был доставлен Новикову.. И Александров тут же начал её разучивать с хором и солистами. И вновь песню ждали проблемы. Сначала выяснилось, что выбранная Новиковым тональность песни была не лучшая для запевалы, поскольку по его замыслу начинать должен был тенор, а подхватывать тему баритон. Солист ансамбля Николай Устинов предложил поменять голоса местами, что и было сделано.
Впервые песня была исполнена в 4 ноября 1944 года на сцене Концертного зале им. П. И. Чайковского Краснознамённым Ансамблем Красной армии под руководством Александра Васильевича Александрова.
Солист - Николай Устинов. Партия аккордеона и второй голос - Виктор Иванович Никитин, знаменитый «Мистер Калинка».
Благодаря прямой трансляции концерта по радио «Смуглянка» сразу ушла в народ. Ее подхватили и на фронте, и в тылу. Её тут же включили в свой репертуар военные ансамбли .«Смуглянка-молдованка», в которой говорилось про партизан Гражданской войны, была воспринята как народная песня о тех, кто героически сражался за освобождение своей многострадальной Родины от немецко-фашистских оккупантов.