«Что вы умеете?» — спросил мэтр. «Все! Петь, танцевать. Декламировать!» — ответила бойкая девушка. «Хорошо, спойте нам что-нибудь!» — попросил Синельников. Аккомпанировал начинающей певице работавший в театре молодой Исаак Дунаевский. Шульженко исполнила песню «Розпрягайте хлопці коней», трагический романс «Шелковый шнурок», русскую народную «По старой калужской дороге» и «Эти платочки» из репертуара эмигрировавшей с белогвардейцами звезды Изы Кремер. Песни были не очень актуальны в 1923 году, Синельников усмехнулся, но в Шульженко способности рассмотрел, а потому зачислил Клавдию в массовку. Драматических ролей она играла немного, зато Синельников начал вставлять в постановки специальные музыкальные номера для песен Шульженко. (Она дебютировала как певица с песней «Звезды на небе» в спектакле «Казнь».) Он же устроил для молодой актрисы уроки вокала с профессором консерватории Чемизовым, который избавил Шульженко от характерного харьковского гэканья с придыханием.
В 1925 году Клавдия Ивановна перешла на работу в Краснозаводский театр. Параллельно с работой в театре Шульженко начала выступать в рабочих клубах, на летних эстрадных площадках. В этот период в ее репертуар входят первые образцы современной бытовой песни — «Шахта № 3» и «Песня о кирпичном заводе» — попросту говоря «Кирпичики». Интересна история этой песни. Ее написал специально для Шульженко киевский поэт Павел Герман, уже известный как автор слов «Авиамарша». На музыку популярного вальсочка «Две собачки» он положил сюжет о парне, девушке и кирпичном заводе. Вскоре после того как Клавдия исполнила эту песенку, ее распевали во всех дворах и пивных Харькова, а затем песня разлетелась по всей стране. Уникальный случай — по сюжету песни «Кирпичики» сняли одноименный художественный фильм. Критика же встретила песню в штыки, называла ее «мещанством» и «похабщиной». Произведения, исполнявшиеся Шульженко, и впоследствии часто находились под ураганным огнем советских «акул пера». Клавдия Ивановна пела обычные, озорные, печальные, бытовые песни, работала в легком жанре, не любила и не хотела включать в репертуар торжественно-патриотические произведения. И естественно, самые знаменитые, самые любимые народом песни назывались в газетах «пошлятиной», «примитивизмом».
В 1927 году композитор Юрий Мейтус пишет специально для харьковской певицы несколько новых произведений — «Красный мак», «Гренада», которые также становятся популярными. В Харькове судьба сводит Шульженко с коренной ленинградкой Елизаветой Резниковой. Елизавета Анисимовна становится аккомпаниатором и на долгие годы верным другом, своеобразным агентом певицы. Именно она убеждает 22-летнюю Шульженко показать себя в столице — вместе Елизавета Анисимовна и Клавдия едут весной 1928 года в Ленинград, где Резниковой с помощью своих связей в артистическом мире города удается устроить дебют Шульженко перед избалованной питерской публикой. Клавдия Ивановна пела на концерте, посвященном Дню печати, в Мариинском театре. Публика провожала харьковчанку со сцены овациями.
Теперь стал возможен и выход в столичный свет. Зимой подруги и соратницы направляются в Москву. В поезде Шульженко знакомится с одесситом, уже опытным артистом эстрады Владимиром Филипповичем Коралли (настоящая фамилия — Кемпер). Заочно они уже были знакомы. Коралли выступал в Харькове, и Клавдия с восторгом смотрела на блестящего чечеточника, хохмача, куплетиста и т. д. и т. п. В момент их встречи между двумя российскими столицами Шульженко уже была помолвлена. Ее женихом был харьковчанин Иван Григорьев — человек без определенного рода занятий, картежник. Клава то переезжала к нему на квартиру, то опять возвращалась к родителям, то сам Григорьев вдруг пропадал на какой-то стройке. Коралли с уверенностью сказал, что приедет в Харьков на свадьбу Шульженко, но в качестве жениха, а не гостя. Так и вышло. Рассказывают, что в Харькове Коралли встретил пару Шульженко-Григорьев, затеял драку с соперником, пригрозил ему пистолетом. Клавдия стала его женой в 1930 году. В мае 1932 года у них родился сын Игорь.
Но сначала было выступление в Москве. В январе 1929 года на сцене мюзик-холла Шульженко с успехом выступила в программе «100 минут репортера». После этого она была приглашена в труппу Ленинградского мюзик-холла, где тогда королем был Леонид Утесов со своим джазом. Артисты быстро нашли общий язык, они оставались друзьями до конца жизни. В репертуаре певицы появились песни «Никогда», «Негритянская колыбельная». В 1929 году Шульженко гастролирует в Киеве, Нижнем Новгороде, принимает участие в программе «Аттракционы в действии». Как и многих ее ленинградских коллег и друзей, ее резко критикуют члены Репертуарного комитета, пришлось делать новую программу с упором на русские и украинские народные песни.
В 1931 году Клавдия Ивановна исполняет одну из главных ролей в пьесе Ленинградского мюзик-холла «Условно убитый», через три года играет в картине «Кто твой друг?» (вместе с мужем, который и пробил для себя и жены эти роли). Правда, фильм был немой, так что Шульженко появилась на экране, но не сделала того, благодаря чему и стала знаменитой. Могла Клавдия Шульженко сняться в фильме «Веселые ребята». По крайней мере, на этом настаивал Утесов, но Александров был непреклонен — страна увидела в роли Анюты Любовь Орлову. Зато в 1936 году Клавдия Шульженко выпустила первую пластинку. К этому моменту помимо всего прочего она уже исполняла танго Ежи Петербургского «Утомленное солнце», песню Поля Марселя (Павла Русакова) «Дружба» («Когда простым и нежным взором») Вскоре последовали песни, написанные влюбленным в Шульженко ленинградским композитором Ильей Жаком, — «Андрюша», «Дядя Ваня». Песни Клавдии Ивановны звучали из сотен дворовых патефонов, на танцах и в ресторанах — они стали символом тех времен. От многих иных артистов Шульженко резко отличала особая, ни с чем не сравнимая душевность исполнения; временами казалось, что она не поет, а говорит — доверительно, вполголоса, как очень близкому другу.
Репрессии 1930-х годов обошли чету Шульженко-Коралли стороной. Кстати, биографы отмечают, что Клавдия Ивановна ни тогда, ни после ни разу не участвовала в коллективной травле тех, кто попадал в опалу, не подписывала резолюций, писем и т. д. и т. п.
В 1937 году Клавдия Шульженко становится солисткой джаз-оркестра под руководством Скоморовского. В репертуаре песни «От края до края», джазовая обработка «Тачанки», «Если Волга разольется», затем «Руки», «Записка», «Челита». Шульженко стремится исполнять сюжетные песни, она «играет песню». Недаром в 1939 году уже широко известная певица приняла участие во Всесоюзном конкурсе артистов эстрады, на котором разделила третью премию с Марией Мироновой.
В январе 1940 года Шульженко организует в Ленинграде уже собственный джаз-оркестр. Выступление нового коллектива решено было сделать театрализованным. В первой программе «Скорая помощь» обыгрывались эпизоды, связанные с организациями, призванными оказывать «скорую помощь» в быту. Вторая целиком строилась на «радиоконферансе». Появилось много шуточных песен: «Курносый», «О любви не говори», «Упрямый медведь», «Нюра».
Война в жизни Клавдии Шульженко — совершенно особый период, наверное, пик творческой биографии. Ее оркестр был преобразован во Фронтовой джаз-оркестр, и начались беспрерывные концерты. Ей удалось чудом увезти из разбомбленного Харькова сына и старого отца. (Вскоре Иван Иванович умер от дистрофии.) Семья ютилась в подвале Дома Красной Армии, отсюда едва ли не каждый день Шульженко отправлялась на работу — давать концерты для солдат. Только за первый год войны Шульженко дала около 500 концертов, она сильно похудела, но артистический паек позволял как-то выживать.
Солдаты же в Шульженко души не чаяли. Под «Давай закурим» плакали самые опытные бойцы. (После концерта они предлагали ей папиросы и страшно удивлялись тому, что певица, оказывается, не курит и не пьет.) А в конце 1941 года в репертуаре Клавдии Ивановны появился знаменитый «Синий платочек». (Певица долго отказывалась исполнять написанный до войны вальсок Ежи Петербургского, пока на одном из концертов какой-то солдат не протянул ей листок с новым текстом. «А музыку Вы, наверное, знаете», — застенчиво произнес молодой поэт.) Песня с новыми словами составила конкуренцию «Катюше» в качестве окопного гимна советских солдат.
Перед бойцами Шульженко поначалу выступала в гимнастерке и пилотке. Но однажды после концерта один офицер попросил ее одеваться в платье: «Бойцам надо отвлечься от войны». С тех пор Шульженко появлялась только в вечернем платье. Ей это было только приятно — она всегда оставалась женщиной до мозга костей. Даже на кухне (когда она позже жила в коммуналке) она не появлялась в халате. Любила флирт, говорят, что изменяла мужу (впрочем, как и он ей). Приобретала только французскую косметику. Главным увлечением певицы было собирание антиквариата, дом был заставлен зеркалами, столиками. Еду предпочитала покупать на рынке, в частности потому, что не хотела получать в магазине что-либо из-под прилавка. Платья для нее шила лучшая московская портниха — от моделей, предлагаемых Москонцертом, она отказывалась с ужасом. С таким же ужасом и порой раздражением воспринимала она свое старение.
В феврале 1942 года певица снялась в фильме «Концерт-фронту», 12 июля 1942 года ей вручили медаль «За оборону Ленинграда». В 1943 году Клавдия Ивановна переехала в Москву, вскоре последовала премьера программы «Города-герои», посвященной 25-летию Красной Армии. Шульженко продолжала давать фронтовые концерты до конца войны. 9 мая 1945 года ей был вручен один из самых престижных боевых орденов — орден Красной Звезды, а в сентябре того же года Шульженко стала заслуженной артисткой РСФСР.
Фронтовой оркестр был расформирован, а сама Клавдия Ивановна испытывала, вероятно, некоторый творческий кризис. Военные песни были не совсем актуальны (она продолжила эту тему в вокальной сюите Соловьева-Седого «Возвращение солдата» в 1947 году), многие песни уже поднадоели, о чем даже печатались эпиграммы в журналах. Возраст опять же. Рассказывают, что в 1952 году Шульженко раздраженно отказалась участвовать в новогоднем концерте, а приглашение исходило от самого Сталина.