Клавдия Ивановна Шульженко родилась 24 (11) марта 1906 года в Харькове.
Брала уроки вокала у профессора Харьковской консерватории Н.Л.Чемизова. В 1923 году начала работать в Харьковском драматическом театре и в том же году дебютировала как певица, исполнив романс "Звёзды на небе" в спектакле «Казнь». Принимала участие во всех дивертисментах, даваемых в театре, параллельно выступая в рабочих клубах и на летних эстрадных площадках города. Исполняемые ею в этот период "Шахта №3"" и Песня о кирпичном заводе" считаются первыми образцами современной бытовой песни.
В 1927 композитор Юлий Мейтус специально для Шульженко написал несколько новых произведений ("Красный мак", "Красная армия", "Гренада"), которые вскоре стали популярными.
Весной 1928 года Шульженко отправляется в Ленинград, где 5 мая, в День печати, принимает участие в концерте для журналистов в Мариинском театре. После успешного дебюта на сцене Московского мюзик-холла в программе «100 минут репортера» в январе 1929 года, дирекция Ленинградского мюзик-холла приглашает Клавдию Шульженко вступить в труппу театра. В репертуаре певицы появляются песни "Никогда", "Негритянская колыбельная", "Физ-культ-ура!".
В 1929 году Шульженко гастролирует в Киеве и Нижнем Новгороде. Вместе со многими известными артистами принимает участие в программе «Аттракционы в действии». После резкой критики со стороны РАПМа и Репертуарного комитета решает испытать себя в новом жанре. С помощью этнографа Э.Паперной отбирает несколько народных песен для новой программы: украинские "И шуме, и гуде", а также "Распрягайте, хлопцы, коней", русскую "Две кукушечки", немецкую "Левый марш" и др. Участвует в театральных постановках.
2 октября 1931 года на сцене мюзик-холла состоялась премьера спектакля «Условно убитый», главные роли в котором исполняли К.Шульженко и Л.Утёсов. Для героини Шульженко Маши Фунтиковой Д.Шостакович написал две песни — "Ах, как приятно вечерком" и "Милый, видишь там и тут…". Режиссер М. Авербах приглашает Шульженко на роль комсомолки Веры в кинофильме «Кто твой друг?». В комедии Э. Иогансона «На отдыхе» певица исполняет лирическую песню за героиню фильма Тоню. Пластинка с записью "Песни Тони" стала фонографическим дебютом Шульженко. В этом же году в студии Заикина были записаны песни "Распрягайте, хлопцы, коней", "До свиданья, тихий Дон", а также написанная специально для Шульженко "Дружба" (Когда простым и нежным взором…). В 1937 году Клавдия Ивановна Шульженко становится солисткой джаз-оркестра под руководством Я.Скоморовского. В первой песенной программе были представлены: "От края и до края" И.Дзержинского, "Если Волга разольется" И.Дунаевского, джазовая интерпретация "Тачанки" К.Листова и др. Большое внимание уделялось новым лирическим произведениям, пришедшим на смену «цыганским» романсам.
В 1938 году в репертуаре певицы появились песни "Руки" И.Жака, "Записка" Н.Бродского, "Челита" Фернандеса.
В 1939 году Шульженко стала лауреатом Первого Всесоюзного конкурса артистов эстрады.
В январе 1940 года был организован джаз-оркестр под управлением Шульженко и В.Коралли. Выступление нового коллектива решено было сделать театрализованным. В первой программе «Скорая помощь» обыгрывались эпизоды, связанные с организациями, призванными оказывать «скорую помощь» в быту. Вторая целиком строилась на «радиоконферансе». Появилось много шуточных песен: "Курносый", "О любви не говори", "Упрямый медведь", "Нюра".
Объявление о начале войны застало певицу на гастролях в Ереване. Добровольно вступив в ряды действующей армии, Шульженко стала солисткой фронтового джаз-ансамбля. За первый год ленинградской блокады дала 500 концертов. В конце 1941 года в репертуаре певицы появилась песня "Синий платочек", ставшая одной из самых популярных песен военного времени. Участвовала в съемках фильма «Концерт фронту», в 1943 году представила программу «Города-герои».
В 1945 году Клавдии Шульженко было присвоено звание заслуженной артистки республики. С лета 1945 года певица стала выступать сольно. Сотрудничала с известными аккомпаниаторами: Л.Фишманом, Б.Мандрусом, Д.Ашкенази.
Стремясь расширить тематику и обогатить форму эстрадной песни, Шульженко в 1947 году обращается к сюите В.Соловьева-Седова "Возвращение солдата" и "Симфоническому вальсу" А.Хачатуряна к драме М.Лермонтова «Маскарад».
С 1950 года сотрудничает с И.Дунаевским, который пишет для певицы "Окрыляющее слово", "Письмо матери", "Школьный вальс", а также песни для фильма с участием Шульженко «Весёлые звезды».
В 60-х годах Шульженко отказалась от многих песен, которые, по мнению певицы, не соответствовали её возрасту, и вновь обратилась к репертуару военных лет. На концерте, посвященном 25-летию битвы под Москвой, исполняла "Давай закурим", "Синий платочек", "Моя тень".
В 1965 году выступила на первом фестивале советской эстрадной песни.
В 1971 году Клавдии Ивановне Шульженко было присвоено звание Народной артистки СССР.
С конца 70-х годов прекращает выступления с сольными программами, принимает участие в сборных концертах. Одной из самых популярных песен ее репертуара в эти годы стала песня "Вальс о вальсе" Э.Колмановского и Е.Евтушенко.
Умерла Клавдия Ивановна 17 июля 1984 года в Москве.