Хотя сама песня «Разговор» появилась в 1944 году, её мелодия была написана годом ранее, когда композитор В. Соловьёв-Седой работал над созданием песни «На солнечной поляночке».

Как мы уже писали, первоначальный вариант мелодии той песни был заменён другим, более подходящим к стихам о «смуглянке-молдаванке». Но отложенный вариант мелодии был вовсе не плохим, просто так выбрасывать его было жалко. Поэтому Василий Павлович как-то раз предложил С. Фогельсону написать под неё стихи:

«Через два дня Фогельсон принёс текст. Я внимательно читал то, что он написал. Стихи, хоть и укладывались в ритм, но не совсем устраивали меня по содержанию.

-  А не могли бы вы написать что-нибудь другое? - спросил я его.

- Есть написать другое! - ответил он по-военному, но не стал спрашивать, что я имею в виду.

Через день Фогельсон принёс другие стихи. Я сказал ему, что в этом втором варианте несколько тем, посоветовал ему выбрать какой-то один образ и через него попытаться передать настроение, которое я хочу выразить музыкой.

- Есть! - сказал он и, повернувшись налево кругом, снова отбыл.

Мы стали встречаться ежедневно. Фогельсон приходил ко мне в гостиницу, где я тогда жил, как на службу. Так мы разработали двадцать вариантов песни. Тринадцатый показался мне подходящим (я не верю в приметы).

В тот день Фогельсон в летнюю ночь», как я прозвал его, был поначалу в подавленном состоянии. Когда он сидел у меня, кто-то позвонил по телефону и пригласил в гости. Я сказал, что приеду со своим соавтором. Фогельсон согласился.

Приехали. Меня попросили что-нибудь сыграть, и я, положив на пюпитр текст Фогельсона, запел «Разговор»... Так была исполнена первая наша песня»

Вскоре песня «Разговор» была записана на пластинку в исполнении Л. Утёсова.