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

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

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

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

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

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

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

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

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

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

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

В тот вечер мне пришлось спеть еще одну песню.