Nathaniel Adams Coles néven jött a világra 1919. március 17-én az Alabama állambeli Montgomeryben, egy hentes fiaként. Születésének időpontjában még az év is bizonytalan, mert az amerikai Délen a szegény családok akkoriban nem sokat bajlódtak az anyakönyvezéssel, ezért sok forrásban 1917 szerepel. Négyéves volt, amikor a család Chicagóba költözött, ahol apja egy baptista gyülekezet lelkésze lett. Zongorázni anyja tanította, aki a templomban orgonált, és a kisfiú igencsak tehetségesnek bizonyult. Tizenkét évesen már Bachot és Rahmanyinovot játszott, de hamarosan a jazz és a blues vonzásába került, legjobban a zongorista Earl Hines hatott rá. Tizenöt évesen hagyta ott az iskolát a zene kedvéért: rögtön egy tizennégy tagú formáció vezetésére vállalkozott, a következő évben bőgős bátyjával alapított szextettet. Az együttes a Broadway egyik fekete színházában kísért egy zenés darabot, amellyel országos turnét is tettek, eközben egy színésznővel egymásba szerettek, s ő tizenhét évesen megnősült.
Los Angelesben telepedett le, bárokban zongorázott, majd 1937-ben megalapította a nevét viselő jazztriót Oscar Moore gitárossal és Wesley Prince bőgőssel, vezetékneve végéről ekkorra már elhagyta az s betűt. A dobost szokatlan módon nélkülöző formáció a hatvanas évek elejéig létezett különböző felállásokban, Cole zongoristaként hatással volt Oscar Petersonra is.
A második világháború után egyre inkább a populáris zene felé fordult, kiváltva a jazzrajongók haragját. Egymást követték széles körben népszerűvé vált felvételei, mint a Sweet Lorraine, a The Christmas Song, a Ramblin Rose, a Mona Lisa, a Love, az It's Only a Paper Moon, az Unforgettable és a Route 66 – utóbbit többen is feldolgozták, köztük Chuck Berry, Tom Petty és a Rolling Stones. Igazi különlegesség volt, amikor 1991-ben, sok évvel Cole halála után a modern technika segítségével Natalie lánya duettként énekelte vele az Unforgettable-t, a produkció Grammy-díjat érdemelt ki. Cole az 1950-es évektől sessionzenészként is dolgozott, egyebek közt olyan legendás művészekkel, mint Louis Armstrong és Ella Fitzgerald, 1961. január 20-án fellépett John F. Kennedy amerikai elnök beiktatási ünnepségén.
Hamarosan maga Cole is a „frontvonalban” találta magát. A fehér felsőbbrendűség híveit dühítette, hogy beperelte azokat a hoteleket, amelyek bőrszíne miatt nem adtak neki szobát, hogy Los Angeles fehérek lakta elővárosában vett házat. Emiatt több bántalmazás is érte, 1956 áprilisában egyik alabamai koncertjén a színpadon támadtak rá. A polgárjogi mozgalom aktivistái azonban éppúgy kritizálták, azt vetették a szemére, hogy nem tesz eleget a feketék egyenjogúságának kivívásáért. A mindkét oldalról érkező támadásokra velősen azt válaszolta, hogy ő zenész, nem aktivista.
Bársonyosan meleg, mély baritonját, kiváló, virtuóz zongorajátékát több mint száz lemezfelvétel őrzi. Pályafutása alatt mintegy hatvan dala került fel a slágerlistára, több listavezető is lett, 1945-ben az ő triójának lemeze vezette a Billboard magazin első albumlistáját. A rendkívül jóképű zenész tucatnyi filmben szerepelt, egyebek közt a St. Louis Bluesban és a Cat Ballou legendájában Jane Fonda és Lee Marvin partnereként, de ez utóbbi bemutatóját már nem érte meg. Rajongott a baseballért, önálló páholya volt a Los Angeles Dodgers stadionjában.
Szenvedélyéért nagy árat fizetett: 1963 decemberében tüdőrákot diagnosztizáltak nála, s 1965. február 15-én, alig negyvenhét évesen meghalt. A zeneipar legnagyobb kitüntetésére, a Grammy-díjra csak egyszer, 1958-ban jelölték, az elismerést 1990-ben posztumusz, életművéért kapta meg. 1993-ban beiktatták a big band és jazzhírességek csarnokába, s a Hollywoodi Hírességek sétányán emlékét két csillag is őrzi, az egyiket televíziós munkájáért, a másikat lemezfelvételeiért kapta.
