Swój debiutancki longplay „Heard it All Before” wydał w 1999 roku w nakładzie zaledwie 500 egzemplarzy. Po latach kopie to stanowią prawdziwe rarytasy na aukcjach kolekcjonerskich.
Trzy lata później do sklepów trafił jego drugi album studyjny – „Pointless Nostalgic”, składający się z typowego wtedy dla artysty repertuaru – standardów jazzowych oraz coverów. Krytycy chwalili perfekcjonizm Culluma, pasję gry na fortepianie oraz odważną próbę zmierzenia się z obarczonymi sławą nagraniami.
W lipcu 2003 roku otrzymał nagrodę Rising Star przyznaną przez amerykańską Akademię Jazzową. Trzy miesiące później wyszła jego kolejna płyta – „Twentysomething”, która szybko pokryła się platyną. Podobnie do poprzedniej – i na tej znalazły się szlagiery jazzowe oraz ballady. Wydawnictwo ogłoszono najlepszym albumem studyjnym jazzowym w Wielkiej Brytanii. Artysta zakończył rok z tytułem najlepiej sprzedającego się w historii jazzowego artysty na Wyspach. By jak najlepiej oddać akustyczną naturę muzyki – zadecydowano o nagraniu i zmiksowaniu wszystkiego w całości na taśmie analogowej. Po zarejestrowaniu materiału okazało się, że nie ma potrzeby cyfrowego korygowania czegokolwiek. Wśród utworów znalazły się między innymi nowe wersje nagrań Gene’a Kelly - „Singin' In The Rain”, klasyk z musicalu „My Fair Lady” – „I Could Have Danced All Night”, utwór Jeffa Buckley’a – „Lover, You Should Have Come Over” oraz Jimiego Hendrixa „Wind Cries Mary”. Płytę promowały dwa single – „All At Sea” oraz „Twentysomething”.
W 2004 roku zdobył nominację do BRIT Awards jako - British Breakthrough Act. Podczas ceremonii rozdania wykonał w duecie z Katie Meluą utwór „The Lovecats” z repertuaru grupy The Cure. A rok później nominowano go do BRIT Awards w kategoriach - Best Male Artist oraz Best Live Act.
Pod koniec września 2005 roku na rynek brytyjski i holenderski trafił kolejny album muzyka - „Catching Tales”. Dwa tygodnie później swoją premierę miał w Stanach Zjednoczonych. Amerykańska i francuska wersja nie zawierały nagrania „Fascinating Rhythm”, które pojawiło się na standardowych europejskich wydaniach. Krążek promowały utwory - „Get Your Way”, „Mind Trick” oraz „Photograph”, do którego tekst powstał w Nowy Rok w domu jego rodziców. Specjalna wersja albumu została poszerzona o dwudziestominutowy dokument, składający się z materiałów zakulisowych oraz pracy w studiu. Limitowaną serię utworu „Get Your Way” wydano natomiast na czerwonej płycie winylowej. Miesiąc po wydaniu krążka – artysta ruszył w trasę koncertową, która zakończyła się dopiero w grudniu następnego roku. W tym czasie wokalista odwiedził Singapur, Hong Kong, Australię i Nową Zelandię, Amerykę Łacińską, Południową Afrykę, Europę, by zakończyć tournee w USA.
W 2007 roku otrzymał The Ronnie Scotts Jazz Award dla Best British Male.
Na początku listopada 2009 roku ukazał się jak dotąd ostatni album artysty – „The Pursuit”. Promował go singiel „I'm All Over It”.
Swoją obecnością uświetnił wiele muzycznych festiwali, jak choćby - Glastonbury (2004), Coachella (2005), South by Southwest (2006), North Sea Jazz ((2006), The Hollywood Bowl ((2006)) oraz Playboy Jazz (2006).
Choć tworzy przede wszystkim w jazzie, w swojej twórczości z powodzeniem łączy różne style i gatunki. Uogólniając, można stwierdzić że prezentuje crossover. Swoje muzyczne inspiracje czerpie z wielu źródeł, od Milesa Davisa i Toma Waitsa począwszy. W młodości grał na perkusji w hip hopowych składach, był gitarzystą w kapelach rockowych (Raw Sausage, The Mystery Machine). Natomiast szeroko znany i ceniony jest jako pianista, a krytycy szczególnie zwracają uwagę na jego styl i zaangażowanie w grę na instrumencie.
Charakterystycznym elementem podczas koncertów jest używanie przez artystę stompboxu, czyli specjalnego pedału (nie mylić z tym, stosowanym przez gitarzystów) wykonanego z bloku drewna, a mającego wzmocnić stukanie stopy o podłoże. Przed laty Jamie znalazł takie urządzenie w Australii i z powodzeniem zaczął wykorzystywać w swoich kompozycjach. Przy tej okazji warto wspomnieć, że to urządzenie stosują także tacy artyści, White Stripes oraz Kanye West. Ponadto często korzysta z maszyny potrafiącej loopować. Zastosował ją między innymi w coverach White Stripes – „Seven Nation Army” i Massive Attack – „Teardrop”. Dodatkowo używa również beatboxingu, czyli wokalnej perkusji, popularnej szczególnie w hip hopie. W większości przypadków jego koncerty są wielką improwizacją i trwają około dwóch godzin.
Na swoim koncie ma współpracę między innymi z Rihanną, Pussycat Dolls, Eltonem Johnem, Joy Division, Radiohead, Gnarlsem Barkley’em, Kylie Minogue, Sugababes, Burtem Bacharachem i Will.I.Amem.
Jimi Hendrix • Katie Melua • The Cure • White Stripes • Kanye West • Massive Attack • Rihanna • Pussycat Dolls • Elton John • Joy Division • Radiohead • Gnarls Barkley • Kylie Minogue • Sugababes • Will.I.Am