Харьковская провинциалка не затерялась в самодостаточной северной столице. Более того, ее первое выступление 5 мая 1928 г. в сборном концерте на сцене Мариинского театра прошло на бис. Вместо положенных двух песен Шульженко исполнила шесть. Пережив «тряски нервное желе», Клавдия поняла, что экзамен прошел успешно. Ее наперебой приглашали с концертами в кинотеатры (по обычаю того времени), а затем она стала выступать в Ленинградском мюзик-холле с Леонидом Утесовым. Благодаря программе «Аттракционы в действии», которая в Ленинграде прошла более сотни раз, Шульженко стала одной из самых популярных актрис в городе. Но приехав на гастроли в Москву, она оказалась на грани провала: жесткая цензура запретила практически все ее песни, даже включая «Гренаду» М. Светлова. Положение на некоторое время спас Утесов, но вскоре певице пришлось подготовить новую программу на основе народных песен. Над каждой из них она, как всегда, много и упорно работала и впоследствии постоянно включала в концерты, помимо русских и украинских, лирические испанские, итальянские и кубинские песни. Так в ее репертуаре появилась «Голубка».
А в конце 1920-х – начале 1930-х гг. певица «копила» песни с лирической интонацией, которые впоследствии критики назвали «жульничествами». Она уже нашла свой стиль исполнения: проникновенное пение сменялось задушевным разговором-исповедью, неожиданными паузами. Иногда фразы произносились чуть ли не шепотом, и зал, замерев, вслушивался в каждое слово. Но исполнение «Встречи», «Портрета» грозило «пожизненной дисквалификацией». Шла борьба за чистоту советской эстрады.
В этот период изменился не только репертуар Шульженко. На гастролях в Нижнем Новгороде в 1929 г. она вновь повстречалась с Владимиром Филипповичем Коралли (настоящая фамилия – Кемпер), популярным куплетистом и чечеточником. Клавдия понимала, что этот мягкий, предупредительный и веселый человек ей более близок, чем мрачный и непонятный, ершистый Григорьев. Но долгое время она не могла излечиться от былой страсти. Соперники встретились за кулисами одного из харьковских театров. Обычная драка чуть не закончилась убийством: Коралли имел право на ношение оружия. Но выстрелить он не успел. Клавдия, услышав слова Григорьева: «Жалкий актеришка!» – сделала свой выбор. Она вернула кольцо и спустя несколько месяцев вышла замуж за Коралли.
Молодожены теперь выступали вместе, но, несмотря на большую популярность Владимира, Клавдия безоговорочно стала лидером в их творческом дуэте. И чем злее была критика, тем восторженней принимала Шульженко публика. Замечательная программа «Условно убитый», поставленная в 1931 г. Л. Утесовым, в прессе была названа «халтурой», но Клавдию это мало интересовало. Она жила в предчувствии материнства и в мае 1932 г. родила в харьковском роддоме (где когда-то появилась сама) своего единственного сына Игоря. А через несколько месяцев уже снималась в фильме «Кто твой друг». Из-за недофинансирования Клавдия лишилась в картине самого главного для нее – звука, а значит, и песен. Этот опыт ей не понравился, и она зареклась сниматься. Единственный раз Шульженко пожалела о своем решении, когда узнала, что вместо нее в «Веселых ребятах» вместе с ее другом Утесовым будет играть и петь песни «Дуни» Любовь Орлова. Но зато в это же время вышла первая граммофонная пластинка: на ней была запись фонограммы «Песни Тони», а за ней последовали «Песня о юге» (или «Утомленное солнце») и «Силуэт». И вообще, уже в предвоенное время билеты на сольные концерты Шульженко раскупались за месяц вперед. Лирические песни «От края до края», «Если Волга разольется» и «Встречи», «Руки», «Вашу записку», «Андрюшу», «Дядю Ваню» и «Челиту» редчайший дар певицы превращал в маленькие спектакли.
И именно с «Челитой» (и «Запиской») Клавдия рискнула выйти на Первый Всесоюзный конкурс артистов эстрады в 1939 г. Ее песню исполняли почти все певицы, но затмить Шульженко никто не смог. Правда, ей досталось всего четвертое место и звание лауреата. А. Райкин, тоже принимавший участие в этом конкурсе, писал: «Для получения первого места ей не хватило нескольких голосов. Время показало: места распределяются не голосованием, а жизнью». Но эта победа позволила Шульженко уйти из джаза Я. Скоморовского и вместе с Коралли создать свой джаз-оркестр. И теперь ее имя знал весь Союз, тиражи пластинок стали миллионными, а потоки писем поклонников достигали неимоверного количества. А с 1940 г. к ним добавились письма и открытки, скромно подписанные инициалами «Г. Е.». Шульженко почему-то относилась к ним с особенной нежностью и даже не подозревала, что их автор, посетив лишь один концерт, стал ее страстным поклонником, покупал все пластинки. И даже через всю войну пронес эти записи в круглой металлической коробке из-под кинопленки.