Большой песенный репертуар и популярность певицы в родном Харькове давали возможность подумать о гастролях. Весной 1928 года она оказалась в Ленинграде. Вот что Клавдия Шульженко вспоминает о тех днях:
"Мне, харьковчанке, привыкшей к теплу, мягкому климату, город на Неве, холодный, весь пронизанный влажностью, показался чужим и неприветливым. Я восхищалась его красотой, но это восхищение было умозрительным и не затрагивало душу. Потом, узнав и поняв строгий характер этого города, по-настоящему привязалась к нему, полюбила его. Тогда же, в мой первый приезд, прогулки по его улицам не очень увлекали меня..."
Первое выступление Шульженко в Ленинграде состоялось 5 мая 1928 года на сцене оперного театра (бывший Мариинский). Это был сборный концерт, в котором наша героиня исполнила две песни: одну на сюжет балета "Красный мак", другую - "На санках". После этого она ушла за кулисы, считая свою программу законченной. Однако она поторопилась. Пришедший следом за ней конферансье Николай Орешков сообщил, что зрители требуют ее на "бис". И Шульженко вновь вышла на сцену. Далее - ее рассказ:
"Еще не осознавая, что это была победа, я спела лирическую песню "Никогда" на слова Павла Германа. И снова успех, и снова Орешков широким жестом приглашает меня на сцену. Пою свою "Папиросницу". Ну, думаю, это последняя. Достаточно. Да и что после нее можно петь? Но аплодисменты не кончаются. Выхожу на поклоны раз, другой, третий.
- Надо петь еще, - шепчет мне Николай Сергеевич.
- Но что? - лихорадочно соображаю я.
Надо спеть такую песню, которая была бы не похожа на предыдущие, и я решаю: буду петь "Колонну Октябрей"...
В тот вечер мне пришлось спеть еще одну песню. Итого - шесть вместо двух запланированных. Экзамен, да еще какой, я выдержала..."
После этого успеха карьера Шульженко резко пошла в гору. Сначала она какое-то время выступала с концертами в кинотеатрах, но ее в том же году пригласили в Ленинградский мюзик-холл. Главным дирижером его был уже хорошо знакомый Шульженко Исаак Дунаевский. А ведущим актером был Леонид Утесов.