В начале 1929 года Шульженко впервые выступила в Москве. Вместе с труппой Ленинградского мюзик-холла она привезла в столицу спектакль "Аттракционы в действии". Наша героиня исполняла в нем лирические песни. Однако петь их ей запретили. В те годы в советском искусстве шла активная критика лирического направления, и под эту кампанию как раз и попала наша героиня. Через год ей уже предложили полностью поменять свой репертуар, исключив из него всю лирику. Шульженко пришлось подчиниться. Она стала исполнять народные песни: украинские, русские, испанские. Так продолжалось до апреля 1932 года, пока свет не увидело постановление ЦК ВКП(б) "О перестройке литературно-художественных организаций", которое ликвидировало РАМП, РАПП и другие организации, диктовавшие законы в тогдашнем искусстве и литературе.

В самом начале 30-х годов, во время поездки с гастролями в Нижний Новгород, в поезде она познакомилась с молодым музыкантом, куплетистом и фельетонистом Владимиром Коралли (настоящая фамилия Кемпер). Молодые люди полюбили друг друга, хотя наша героиня в то время уже была помолвлена с другим и носила на руке обручальное кольцо, подаренное им. Но ее это не остановило. Сразу после тех гастролей Шульженко кольцо сняла и вернула его своему, теперь уже бывшему, жениху. А вскоре к ее родителям в Харьков приехал В. Коралли. Был он в роскошной шубе из беличьих хвостиков, которая делала его еще привлекательнее и импозантнее. Согласие на свадьбу молодые получили. В 1932 году у них родился сын, которого назвали Георгием.

В 1935 году свет увидела первая пластинка с записью песни в исполнении Шульженко. Как это произошло, вспоминает сама певица:

"Случилось так, что моя самая первая пластинка появилась без моего участия. Друзья принесли мне домой на Кировский проспект новый черный диск, поставили его на патефон, и я услышала свой голос. Не буду говорить о своих ощущениях - аналогичные возникают у каждого, кто впервые слышит себя со стороны - "это не я"! Но песня была моя, и кое-какие интонации я тоже признала! С удивлением рассматривала этикетку. Фамилия исполнителя на ней отсутствовала. "Песня Тони. Ленкино" - значилось там, а ниже шла необычная расшифровка: "Воспроизведено с кинопленки по способу изобретателей Абрамович, Заикина и Товстолеса".

И тут мне стало ясно. Незадолго до появления анонимной пластинки режиссер Ленкино Эдуард Юльевич Иогансон пригласил меня принять участие в звуковой кинокомедии "На отдыхе". Но пригласил не сниматься, а только петь за исполнительницу главной женской роли.

Музыку к фильму написал известный композитор Иван Дзержинский, который, насколько мне известно, нечасто обращался к жанру лирической песни. Но его "Песня Тони" была удивительно хороша, и я согласилась ее спеть. Фонограмму с моим исполнением записали до начала съемок, а потом уже на съемочной площадке героине только оставалось прилежно открывать рот и внимательно следить за артикуляцией, чтобы зрители впоследствии не заметили, что она поет буквально не своим голосом. Кажется, это был первый случай совмещения чужой фонограммы с изображением, совмещения, которое столь часто практикуется сегодня. В ту же пору, о которой я рассказываю, способ этот держался в секрете, и изобретатели записи пластинок с кинопленки не рискнули, выпуская "Песню Тони", выступить в роли разоблачителей!"

Стоит отметить, что еще в 1933 году Шульженко могла сняться в одной из главных ролей в фильме "Кто твой друг?". Музыку к картине написал И. Дунаевский, который, собственно, и пригласил ее на съемки. Однако из этой затеи ничего не получилось. На киностудии "Белкино" был всего один комплект звуковой аппаратуры, и этот комплект достался другой съемочной группе. А жаль...

Между тем в 1936 - 1939 годах Шульженко активно концертировала по стране вместе с джаз-оркестром Я. Скоморовского. Ее популярность росла от концерта к концерту. В декабре 1939 года ее пригласили участвовать в 1-м Всесоюзном конкурсе артистов эстрады (он проходил в Колонном зале Дома союзов, и в нем принимали участие многие будущие звезды советской эстрады: А. Райкин, М. Миронова, К. Джапаридзе и др.). В конкурсе вокала вместе с нашей героиней в первом туре выступали 160 человек. К третьему туру их уже осталось 12. Среди этих счастливчиков была и Шульженко.

Решающее для нее выступление на конкурсе состоялось 16 декабря. Она исполнила три обязательные песни и собиралась было уйти со сцены, когда зал внезапно взорвался аплодисментами. Слушатели стали просить певицу исполнить еще одну песню на "бис" (и это при том, что "бисы" на конкурсе были запрещены). Наша героиня поначалу растерялась, но затем, увидев счастливое лицо И. Дунаевского, который возглавлял жюри конкурса, решилась и вновь вышла на сцену. Она исполнила "Записку", и после нее зал вновь взорвался аплодисментами. Это был триумф Клавдии Шульженко.

Сразу после блестящего выступления на этом конкурсе Шульженко и ее мужу Коралли было предложено организовать джаз-ансамбль. Дебют этого ансамбля состоялся в январе 1940 года, когда нашу героиню пригласили в Государственный дом звукозаписи, чтобы записать ее первую настоящую пластинку. В течение шести часов были записаны три ее шлягера: "Записка", "Андрюша" и танго "Встречи".

Начало войны Шульженко встретила в Ереване, где была на гастролях. После них она намеревалась вместе с мужем и восьмилетним сынишкой (он тогда жил у бабушки с дедушкой в Харькове) отправиться на отдых к морю. Но этим планам не суждено было сбыться. Гастроли были прерваны, и артисты срочно отправились в Ленинград. Далее - слово Клавдии Шульженко:

"В Харькове поезд остановился далеко от вокзала - в городе была объявлена воздушная тревога. И тут совершенно неожиданно в стоящем неподалеку от нас поезде мы повстречали нашего сына. Этим поездом в Ленинград возвращался Аркадий Райкин с Театром миниатюр, прервавшим свои харьковские гастроли, и мои родственники передали артистам Гошу, чтобы его доставили домой. Мне сразу стало легче дышать - матери поймут меня.

Поезд вез нас дальше, навстречу войне. Нам уже попадались беженцы из западных областей Украины, Белоруссии, из Прибалтики, где шли ожесточенные бои. И вот Ленинград. Как быстро изменилось все - и сам город, и люди, живущие в нем. Мешки с песком, укрывшие витрины бывшего Елисеевского гастронома и кафе "Норд" на Невском, заклеенные белыми бумажными крестами окна жилых домов, большие клещи, бочки с водой и ящики с песком в каждом подъезде - для тушения зажигательных авиабомб (зажигалок, как их называли), дежурные с противогазами на боку, воздушные тревоги и сосредоточенные, посерьезневшие лица, на которых не было и тени паники. Чувствовалось, что город готовился к сражению.