Lyttelton a London melletti Eton College-ban született, ahol később tanulmányait is végezte. 13 évesen vett először trombitát a kezébe, ezután viszont elválaszthatatlan volt a hangszerétől. A New Orleans-i dixieland stílusa vonzotta leginkább, eleinte Charles Webb zongorista együttesében játszott, majd saját formációt alakított, amelyhez olyan vendégelőadókat hívott, mint Sidney Bechet. Amikor 1956-ban Bad Penny Blues című felvétele bekerült a Top 20-ba, hazájában a jazz legnagyobb sikerét hozta, közben viszont a hagyományos műfajtól eltávolodott, és swinget kezdett játszani, amely miatt sok rajongója felháborodott. A puristákkal mit sem törődve folytatta a mainstream jazz játékot, sőt ő volt az első brit jazz zenész, aki karibi ritmusokat alkalmazott szerzeményeiben. Fúvósszekciójában olyan zenészek kaptak helyet, mint Tony Coe altszaxofonos, Jimmy Skidmore tenorszaxofonos, és Joe Temperley baritonszaxofonos. Rendkívüli sikerének köszönhetően 1988-ban, amikor 40 éve volt a pályán, már 10.000 fellépést tudott maga mögött, de ezt követően, rádiós műsorvezetői ténykedése alatt is folyamatosan muzsikált, egészen idén márciusig.
