В то же время Шульженко начала участвовать в дивертисментах, концертных отделениях, устраиваемых после спектакля. Подобные дивертисменты в те годы были обязательным явлением в театрах, в них актеры имели возможность проявить себя в смежных областях: песне, монологе, стихах.

Существенный поворот в судьбе Шульженко произошел в 1924 году, после встречи с известной оперной певицей Лидией Липковской. В том году она приехала с гастролями в Харьков, и, побывав на ее концерте, Шульженко пришла в восторг от ее таланта. На следующий день после концерта Клава набралась смелости и пришла к Липковской в гостиницу. Послушав несколько песен в исполнении нашей героини, певица сказала: "У вас настоящий лирический дар. "Жесткие" песни, типа "Шелкового шнурка", вам неуместны. Вам нужен свой репертуар, соответствующий вашему дарованию..."

Эти слова окрылили Шульженко, и она загорелась идеей создать для себя настоящую песенную программу. Но как это сделать? И тут ей помог случай.

В один из дней к ней в театр пришел молодой человек и представился поэтом Павлом Германом. (Это именно он написал популярный в те годы "авиамарш" "Мы рождены, чтоб сказку сделать былью".) Он сообщил, что у него написано несколько новых песен, и он предлагает их исполнить Шульженко. Среди них были: "Записка", "Не жалею", "Настанет день" и др. Наша героиня согласилась. Летом 1925 года, когда она согласилась сыграть несколько спектаклей в Краснозаводском драмтеатре, с ней завязали тесные творческие отношения композитор Юлий Мейтус и молодой актер, по совместительству поэт Евгений Брейтиган. Так день за днем у Шульженко набирался собственный песенный репертуар.

Песенная слава к нашей героине приходила постепенно. Однако настоящий успех пришел к ней после того, как она исполнила две песни, написанные композитором Валентином Кручининым и поэтом Павлом Германом. Это были: "Песня о кирпичном заводе" (в народе - "Кирпичики") и "Шахта № 3". Вот что вспоминала об этом сама Клавдия Шульженко: "Песня о кирпичном заводе", ставшая вскоре одиозной, действительно не отличалась ни музыкальными, ни поэтическими достоинствами. Композитор Кручинин обработал для нее мелодию известного вальса, который считался чуть ли не народным. Этот вальс можно было услышать в цирке, в балагане, его играли шарманщики. Я слыхала эту мелодию в детстве. Дома у нас был граммофон, и среди многочисленных пластинок к нему был и вальс "Две собачки", который я сразу вспомнила, услышав новую песню В. Кручинина.

Не нужно думать, что речь идет о непреднамеренном плагиате. Нет, Павел Герман рассказывал мне позже, что они с Кручининым долго искали мелодию, которая легко бы узнавалась, легко запоминалась, была бы доступна. Таким же доступным был и текст песни, который мало чем отличался от тех, прямо скажем, примитивных песен городских окраин, которые широко бытовали в начале века, а некоторые, как, например, "Маруся отравилась", распевались еще и в 20-е годы...

Павел Герман, широко образованный человек, хорошо знавший русскую и зарубежную поэзию, умевший писать тонкие лирические стихотворения, и Валентин Кручинин, талантливый музыкант, не поднялись здесь выше вкуса своих слушателей, даже, вероятно, я бы сказала, сознательно потакали его неразвитости. Но они, и в этом их заслуга, впервые обратились, пусть не во всем удачно, к современной бытовой теме...

"Кирпичики" подхватили сразу. Помню, как после первого же моего исполнения этой песни в одном из рабочих клубов на шефском концерте ко мне подошли девушки в красных косынках - комсомолки и ребята - рабочие этого предприятия. Они попросили "не пожалеть времени и дать списать слова понравившейся песни". Такая картина повторялась не однажды".

Большой песенный репертуар и популярность певицы в родном Харькове давали возможность подумать о гастролях. Весной 1928 года она оказалась в Ленинграде. Вот что Клавдия Шульженко вспоминает о тех днях:

"Мне, харьковчанке, привыкшей к теплу, мягкому климату, город на Неве, холодный, весь пронизанный влажностью, показался чужим и неприветливым. Я восхищалась его красотой, но это восхищение было умозрительным и не затрагивало душу. Потом, узнав и поняв строгий характер этого города, по-настоящему привязалась к нему, полюбила его. Тогда же, в мой первый приезд, прогулки по его улицам не очень увлекали меня..."

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

"Еще не осознавая, что это была победа, я спела лирическую песню "Никогда" на слова Павла Германа. И снова успех, и снова Орешков широким жестом приглашает меня на сцену. Пою свою "Папиросницу". Ну, думаю, это последняя. Достаточно. Да и что после нее можно петь? Но аплодисменты не кончаются. Выхожу на поклоны раз, другой, третий.

- Надо петь еще, - шепчет мне Николай Сергеевич.

- Но что? - лихорадочно соображаю я.

Надо спеть такую песню, которая была бы не похожа на предыдущие, и я решаю: буду петь "Колонну Октябрей"...

В тот вечер мне пришлось спеть еще одну песню. Итого - шесть вместо двух запланированных. Экзамен, да еще какой, я выдержала..."

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

Первыми представлениями, в которых наша героиня выступила в составе труппы мюзик-холла, были: сборные концерты "100 минут репортера" и "Аттракционы в действии". А в 1931 году она наконец получила свою главную роль - в спектакле "Условно убитый" она сыграла подружку телеграфиста Курочкина (Л. Утесов) по имени Машенька Фунтикова. Музыку к этому спектаклю написал молодой тогда Д. Шостакович.