Elle est née le 24 mars (11 mars, selon l'ancien style) 1906 à Kharkov dans la famille d'Ivan Ivanovitch Chouljenko, comptable à la Direction générale des chemins de fer.
Klavdiya a commencé à interpréter des chansons folkloriques à la fin des années 1920. En 1923, elle est entrée au Théâtre dramatique de Kharkov sous la direction de N.N. Sinelnikov. La même année, Klavdiya Chouljenko a fait ses débuts comme chanteuse en interprétant la romance « Étoiles dans le ciel » dans la pièce « Exécution ». À l'été 1925, elle a commencé à travailler au Théâtre dramatique de Krasnozavodsk à Kharkov. En 1928, Klavdiya a fait ses débuts sur la scène du Théâtre Mariinsky de Leningrad lors d'un concert dédié à la Journée de la presse. En janvier 1929, elle a fait ses débuts au Music-Hall de Moscou. En 1930, Klavdia Chouljenko épousa Vladimir Koralli et, en mai 1932, leur fils Igor naquit.
En octobre 1931, le Music-Hall de Leningrad accueillit la première de la pièce « Meurtres sous conditions », où Klavdia Chouljenko interprétait le rôle de Machenka Funtikova. La musique de cette pièce fut écrite par Dmitri Chostakovitch, et Isak Dunaevsky était chef d'orchestre. En 1934, K. Chouljenko joua le rôle de Vera dans le film « Qui est ton ami ?» réalisé par M. Averbakh. Ses premiers enregistrements furent réalisés en 1936.
En janvier 1940, un orchestre de jazz dirigé par Klavdia Chouljenko et Vladimir Koralli fut créé à Leningrad. Il devint très populaire et exista jusqu'à l'été 1945. Dès le premier jour de la Grande Guerre patriotique, l'Orchestre de jazz devint l'Ensemble de jazz de première ligne, avec lequel Klavdiya Shulzhenko se produisit pour les soldats du front de Leningrad, directement au front. Pendant le siège de Leningrad, K. Shulzhenko donna plus de 500 concerts pour les soldats. Grâce à son interprétation de chansons du front, telles que « Le Mouchoir bleu », « Fumons », « Amis-frères », entre autres, Klavdiya Shulzhenko reçut la reconnaissance de toute l'Union. Le 12 juillet 1942, le 500e concert de K. I. Shulzhenko et de l'Ensemble de jazz de première ligne eut lieu sur la scène de la Maison de l'Armée rouge de Leningrad. À l'occasion de ce concert, la chanteuse reçut la médaille « Pour la défense de Leningrad ».
Avec l'ensemble de jazz, Klavdiya effectua des tournées avec les troupes d'active tout au long de la guerre. Le 9 mai 1945, Klavdiya Chouljenko reçut la plus haute distinction militaire soviétique : l’Ordre de l’Étoile Rouge. Le 29 septembre 1945, Klavdiya Chouljenko, soliste de l’Association panrusse de tournées et de concerts, reçut le titre honorifique d’Artiste émérite de la RSFSR pour ses réalisations exceptionnelles dans le domaine de l’art vocal.
Après la guerre, Klavdiya Chouljenko poursuivit ses concerts. En 1954, son premier LP sortit. En mars 1954, elle joua dans le film « Étoiles joyeuses », réalisé par V. Stroeva. La même année, Klavdiya divorça de Koralli et épousa deux ans plus tard le caméraman Gueorgui Epifanov. En novembre 1962, Klavdiya Chouljenko reçut le titre honorifique d’Artiste du peuple de la RSFSR pour ses réalisations exceptionnelles dans le domaine de l’art populaire soviétique.
En octobre 1965, Klavdia Ivanovna participa au premier Festival de chansons de variétés soviétiques, qui se tint au Théâtre des Variétés d'État de Moscou. Deux ans plus tard, en 1967, elle devint membre du jury de ce festival. En mai 1971, « pour ses grandes réalisations dans le domaine de l'art des variétés soviétiques », la soliste du Mosconcert K. I. Chouljenko reçut le titre honorifique d'Artiste du peuple de l'URSS par décret du Présidium du Soviet suprême de l'URSS, et en juin 1976, l'Ordre de Lénine.
En 1980, Chouljenko enregistra son dernier disque vinyle longue durée, «Portrait». La même année, l'édition Molodaïa Gvardiya publia ses mémoires, « Quand tu me demandes… » (enregistrement littéraire de Gleb Skorokhodov). En décembre 1983, Klavdia Ivanovna a participé au tournage du téléfilm « Klavdia Chouljenko vous invite », réalisé par S. Zhuravlev, diffusé en première le 18 décembre sur la Première chaîne de la Télévision centrale.
Artiste émérite de la RSFSR (1945).
Artiste du peuple de la RSFSR (1962).
Artiste du peuple de l'URSS (1971).
Décédée le 17 juin 1984 à Moscou.
Inhumée au cimetière de Novodievitchi.
