Laine ryhtyi laulamaan ammattimaisesti vasta parikymppisenä. Hänen varhaisia vaikutteita laulajana olivat Ella Fitzgerald, Sarah Vaughan, Judy Garland ja Lena Horne. Hän pääsi 24-vuotiaana menestyksekkäästi John Dankworthin pienryhmään, Dankworth Seveniin, ja myöhemmin tämän orkesteriin, jonka kanssa hän esiintyi vuoteen 1958 asti. Dankworth ja Laine avioituivat samana vuonna salaa Hampsteadin maistraatissa. Ainoat todistajat olivat pariskunnan ystävä, pianisti Ken Moule, ja Dankworthin sovittaja David Lindup. Pariskunnalla oli kaksi lasta, jotka molemmat ovat menestyneitä muusikoita: Alec, joka asuu Yhdysvalloissa, ja Jacqui, brittiläinen laulaja, joka on julkaissut useita albumeita.
Hän näytteli pääosan uudessa näytelmässä Lontoon Royal Court -teatterissa, joka oli 1950-luvun uuden aallon näytelmäkirjailijoiden, kuten John Osbornen ja Harold Pinterin, kotipaikka. Tämä johti muihin näyttämötehtäviin, kuten musikaaliin Valmouth vuonna 1959, näytelmään A Time to Laugh (yhdessä Robert Morleyn ja Ruth Gordonin kanssa) vuonna 1962, Boots With Strawberry Jamiin (yhdessä John Nevillen kanssa) vuonna 1968 ja lopulta hänen rooliinsa Julie La Vernenä Wendy Toyen ohjaamassa Show Boat -näytelmässä lontoolaisessa Adelphi Theatre -teatterissa vuonna 1971. Show Boat oli tähän asti pisin esityskautensa tuolla Lontoon kaudella, jolloin sitä esitettiin 910 kertaa.
Tänä aikana hänellä oli kaksi merkittävää levytysmenestystä. ”You’ll Answer to Me” pääsi Britannian Top 10:een, kun Laine oli ”prima donna” vuoden 1961 Edinburghin festivaalien produktiossa Kurt Weillin ooppera/baletti Seitsemän kuolemansyntiä, jonka ohjasi ja koreografioi Kenneth MacMillan. Vuonna 1964 hänen Shakespeare and All that Jazz -albuminsa Dankworthin kanssa sai hyvän vastaanoton. Dankworth ja Laine perustivat Stables-teatterin vuonna 1970 vanhaan tallirakennukseen, joka sijaitsi heidän kotinsa alueella. Se oli välitön menestys, ja ensimmäisenä vuonna annettiin 47 konserttia.
Lainen kansainvälinen toiminta alkoi vuonna 1972 onnistuneella ensimmäisellä Australian-kiertueella, jolla hän julkaisi 1970-luvun aikana kuusi top-100-albumia. Pian tämän jälkeen hänen uransa Yhdysvalloissa käynnistyi konsertilla New Yorkin Lincoln Centerissä, jota seurasi vuonna 1973 ensimmäinen monista Carnegie Hallin esiintymisistä. Pian seurasivat rannikolta rannikolle suuntautuvat kiertueet Yhdysvalloissa ja Kanadassa, ja niiden myötä levytykset ja televisioesiintymiset, kuten The Muppet Show vuonna 1977. Tämä johti useiden ehdokkuuksien jälkeen hänen ensimmäiseen Grammy-palkintoonsa, joka myönnettiin tunnustuksena Carnegie-konsertin livetallenteesta vuodelta 1983. Hän on jatkanut säännöllisiä kiertueita, muun muassa Australiassa vuonna 2005.
Hän on tehnyt yhteistyötä James Galwayn, Nigel Kennedyn, Julian Lloyd Webberin ja John Williamsin kanssa. Muita tärkeitä levytyksiä tuona aikana olivat duettoalbumit Ray Charlesin kanssa (Porgy and Bess) sekä Arnold Schönbergin Pierrot Lunaire, josta hän sai Grammy-ehdokkuuden.
Lainen suhde musiikkiteatteriin alkoi Isossa-Britanniassa ja jatkui Yhdysvalloissa tähtinäytöksillä Sondheimin Pieni yömusiikki (A Little Night Music) -teoksessa ja Franz Lehárin Iloinen leski -teoksessa (Michiganin ooppera). Vuonna 1980 hän näytteli Dankworthin musikaalissa Colette. Esitys alkoi Stables-teatterissa Wavendonissa vuonna 1979 ja siirtyi Comedy Theatreen Lontoossa syyskuussa 1980. Vuonna 1985 hän näytteli prinsessa Pufferin roolin Broadway-musikaalissa The Mystery of Edwin Drood, josta hän sai Tony-ehdokkuuden. Vuonna 1989 hän sai Los Angelesin kriitikoiden tunnustuksen noitan roolistaan Sondheimin Into the Woodsissa.
Toukokuussa 1992 Laine esiintyi Frank Sinatran kanssa viikon konsertissa Lontoon Royal Albert Hallissa.
1990-luvun loppupuolella Laineen konsertit olivat loppuunmyytyjä eri puolilla maailmaa, yleensä Dankworthin tukemana bändinsä, orkesterinsa tai pienemmän ryhmänsä kanssa. Hänen tavalliseen yhtyeeseensä kuuluivat John Horler (piano), Alec Dankworth (basso), Allan Ganley (rummut) ja Mark Nightingale (pasuuna).
Lainen omaelämäkerta Cleo julkaistiin syyskuussa 1994 Simon & Schusterin kustantamana. Hänen toisen kirjansa You Can Sing If You Want To julkaisi Victor Gollancz lokakuussa 1997. Vuonna 2000 hän esiintyi laulaja Gweninä elokuvassa The Last of the Blonde Bombshells.
Vuoden 1997 uudenvuoden kunniamainosluettelossa Laineesta tuli komentajakuningattaren (Dame Commander) ja hänet nimitettiin muotoon Dame Cleo Laine DBE. Vuoden 2006 New Year’s Honours -luettelossa hänen miehestään tehtiin ritari poikamies, josta tuli Sir John Dankworth. He olivat yksi harvoista pariskunnista, joissa molemmat osapuolet saivat arvonimen omana itsenään, ja ainoa jazzin pariskunta, joka sai tällaisen tunnustuksen.
Dankworth kuoli 6. helmikuuta 2010, tunteja ennen suunniteltua konserttia Stables-teatterissa Wavendonissa juhlistamaan paikan 40-vuotispäivää. Hän oli ollut sairaana useita kuukausia Yhdysvalloissa järjestetyn konserttikiertueen jälkeen. Surustaan huolimatta Laine esiintyi 40-vuotisjuhlakonsertissa yhdessä John Dankworth Big Bandin ja useiden perheenjäsentensä kanssa – ja ilmoitti hänen kuolemastaan vasta lopuksi. Laineen päätös esiintyä oli sanomalehtien etusivuilla ympäri maailmaa, muun muassa The Timesin etusivulla oli koko kuva hänestä.
Viikko Dankworthin kuoleman jälkeen Laine tuurasi edesmennyttä miestään ja esiintyi jälleen konsertissa Pinnerissä Luoteis-Lontoossa. Laine jatkoi esiintymistä ja haastattelujen antamista Dankworthin kuoleman jälkeisinä kuukausina. Hän esiintyi pääesiintyjänä Music in the Garden -festivaalilla Wavendonissa kesä- ja heinäkuussa 2010.
Maaliskuussa 2010 Laineen ja Dankworthin viimeinen musiikillinen yhteistyö julkaistiin CD:llä ja ladattavana – Jazz Matters. Levyllä Dankworth Big Band soitti Dankworthin uusia sävellyksiä, jotka Dankworth oli kirjoittanut pariskunnan esiintymistä varten vuoden 2007 Proms-konsertissa Royal Albert Hallissa.
Laine on kuuluisa paitsi tulkintatyylistään, myös lähes neljän oktaavin äänialastaan ja laulullisesta sopeutumiskyvystään. Syvien sielukkaiden sävelten lisäksi Laineen scattingista ja yläsävelistä on tullut hänen tavaramerkkinsä. Vaikka hänen luonnollinen äänialansa on altto, hän pystyy tuottamaan G:n korkeamman kuin korkean C:n. Sunday Timesin Derek Jewel tituleerasi häntä ”yksinkertaisesti maailman parhaaksi laulajaksi.”