Laine csak a húszas évei közepén kezdett el hivatásszerűen énekelni. Korai énekesnői hatásai Ella Fitzgerald, Sarah Vaughan, Judy Garland és Lena Horne voltak. 24 éves korában sikeresen felvételizett John Dankworth kis csapatába, a Dankworth Sevenbe, majd később a zenekarába, amellyel 1958-ig lépett fel. Dankworth és Laine még abban az évben titokban összeházasodtak a Hampstead-i anyakönyvi hivatalban. Az egyetlen tanú a pár barátja, a zongorista Ken Moule és Dankworth hangszerelője, David Lindup volt. A párnak két gyermeke született, akik mindketten sikeres zenészek: Alec, aki az Egyesült Államokban él, és Jacqui, egy brit énekesnő, aki számos albumot adott ki.
A londoni Royal Court Színházban, az 1950-es évek új drámaírói hullámának, például John Osborne-nak és Harold Pinternek az otthonában, egy új darab főszerepét játszotta. Ez további színpadi fellépésekhez vezetett, mint például 1959-ben a Valmouth című musical, 1962-ben az A Time to Laugh (Robert Morley-val és Ruth Gordonnal), 1968-ban a Boots With Strawberry Jam (John Neville-lel), és végül 1971-ben a londoni Adelphi Theatre-ben a Show Boat című Wendy Toye-produkcióban Julie La Verne szerepét játszotta. A Show Boat abban a londoni évadban volt az eddigi leghosszabb futása, 910 előadással.
Ebben az időszakban két jelentős lemezfelvételi sikert aratott. A “You’ll Answer to Me” eljutott a brit top 10-be, míg Laine “primadonna” volt Kurt Weill A hét halálos bűn című operájának/balettjének 1961-es Edinburgh-i Fesztivál produkciójában, melyet Kenneth MacMillan rendezett és koreografált. 1964-ben a Dankworth-szel közös Shakespeare and All that Jazz című albuma jó fogadtatásban részesült. Dankworth és Laine 1970-ben megalapították a Stables színházat a házuk területén lévő régi istállóépületben. Azonnali sikert aratott, az első évben 47 koncertet adtak.
Laine nemzetközi tevékenysége 1972-ben kezdődött, egy sikeres első ausztrál turnéval, ahol az 1970-es évek során hat top-100-as albumot adott ki. Nem sokkal később karrierje az Egyesült Államokban egy New York-i Lincoln Centerben adott koncerttel indult, majd 1973-ban következett az első a sok Carnegie Hall-beli fellépés közül. Hamarosan partról partra tartó turnék következtek az Egyesült Államokban és Kanadában, majd lemezalbumok és televíziós szereplések sora, köztük 1977-ben a The Muppet Show-ban. Ez vezetett több jelölés után első Grammy-díjához, amelyet 1983-as Carnegie-koncertjének élő felvételéért kapott. Azóta is rendszeresen turnézik, többek között 2005-ben Ausztráliában.
Munkája során együttműködött James Galwayjel, Nigel Kennedyvel, Julian Lloyd Webberrel és John Williamsszel. További fontos felvételei ebben az időszakban a Ray Charles-szal készített duettalbumok (Porgy és Bess), valamint Arnold Schönberg Pierrot Lunaire című műve, amelyért Grammy-díjra jelölték.
Laine kapcsolata a zenés színházzal Nagy-Britanniában kezdődött, és az Egyesült Államokban folytatódott Sondheim Egy kis éji zenében és Lehár Ferenc A víg özvegyében (Michigan Opera) nyújtott főszerepekkel. 1980-ban főszerepet játszott a Colette című Dankworth-musicalben. Az előadás 1979-ben kezdődött a Stables színházban, Wavendonban, és 1980 szeptemberében került át a londoni Comedy Theatre-be. 1985-ben ő alakította Puffer hercegnő szerepét a The Mystery of Edwin Drood című Broadway-musicalben, amelyért Tony-jelölést kapott. 1989-ben a Los Angeles-i kritikusok elismerését kapta a boszorkány alakításáért Sondheim Into the Woods című darabjában.
1992 májusában Laine Frank Sinatra oldalán lépett fel egy héten át a londoni Royal Albert Hallban.
A kilencvenes évek végére Laine koncertjei világszerte teltházasak lettek, általában Dankworth zenekarával, zenekarával vagy kisebb csoportjával támogatta. Szokásos zenekara John Horler (zongora), Alec Dankworth (basszusgitár), Allan Ganley (dob) és Mark Nightingale (harsona) volt.
Laine önéletrajza, a Cleo 1994 szeptemberében jelent meg a Simon & Schuster kiadónál. Második könyve, a You Can Sing If You Want To, 1997 októberében jelent meg a Victor Gollancz kiadónál. 2000-ben Gwen énekesnőként szerepelt Az utolsó szőke bombázók című filmben.
Az 1997-es újévi kitüntetések listáján Laine Dame Commander lett, és Dame Cleo Laine DBE címet kapott. A 2006-os New Year’s Honours listán férjét lovaggá ütötték, Sir John Dankworth lett. Ők voltak azon kevés párok egyike, ahol mindkét partner saját jogán viselte a címet, és az egyetlen pár a jazzben, akiket így ismertek el.
Dankworth 2010. február 6-án halt meg, órákkal azelőtt, hogy a wavendoni Stables színházban a helyszín 40. évfordulóját ünneplő tervezett koncertet tartották volna. Több hónapig betegeskedett egy amerikai koncertkörutat követően. Gyásza ellenére Laine fellépett a 40. évfordulós koncerten a John Dankworth Big Banddel és több családtagjával együtt – csak a végén jelentette be a halálát. Laine döntése, hogy fellép, világszerte az újságok címlapjain szerepelt, többek között a The Times címlapjára került egy teljes fotó róla.
Egy héttel Dankworth halála után Laine beugrott néhai férje helyett, és ismét koncertezett az északnyugat-londoni Pinnerben. Laine a Dankworth halálát követő hónapokban is folytatta a fellépéseket és interjúkat adott. 2010 júniusában és júliusában a Music in the Garden fesztivál fő fellépőjeként lépett fel Wavendonban.
2010 márciusában Laine és Dankworth utolsó zenei együttműködése megjelent CD-n és letölthető formában – Jazz Matters. A felvételen a Dankworth Big Band új kompozíciókat játszott, amelyeket Dankworth a páros 2007-es Proms előadására írt a Royal Albert Hallban.
Laine nemcsak interpretációs stílusáról, hanem közel négy oktávos hangterjedelméről és hangi alkalmazkodóképességéről is híres. Amellett, hogy mély, soulos hangokat üt meg, Laine skatulyázása és csúcshangjai is a védjegyévé váltak. Bár természetes hangterjedelme az alt, képes a magas C fölötti G-t is megszólaltatni. Derek Jewel a Sunday Times-tól “egyszerűen a világ legjobb énekesnőjének” nevezte őt.