Az Alabama állambeli Montgomeryben jött a világra 1919. március 17-én Nathaniel Adams Coles néven, egy hentes fiaként. 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 dzsessz és a blues vonzásába került, legjobban a zongorista Earl „Fatha” Hines hatott rá.
Tizenöt évesen hagyta ott az iskolát a zene kedvéért: rögtön egy 14 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, és Nat az országos turnéra is elkísérte őket. Az egyik színésznővel egymásba szerettek, s ő 17 évesen megnősült.
Los Angelesben telepedett le, bárokban zongorázott, majd 1937-ben megalapította a nevét viselő dzsessztrió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ásban, Cole zongoristaként hatással volt Oscar Petersonra is. A „King” becenevet a legenda szerint egy klubtulajdonostól kapta, aki egy fellépésük után elismerése jeléül ezüstkoronát tett fejére. Érdekesség, hogy amikor a Billboard magazin 1945-ben közzétette első albumlistáját, annak élén a Nat King Cole trió egyik albuma állt.
A második világháború után egyre inkább a popzene felé fordult, kiváltva a dzsesszrajongó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, 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 sessionz-ené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.