Nathaniel Adams Coles kam am 17. März 1919 als viertes Kind des Baptisten-Predigers Edward Coles und Perlina Adams Coles in Montgomery/Alabama zur Welt. Als Nat vier Jahre alt war, packte die Familie ihre Habseligkeiten und ließ die Armut und Segregation des"Baumwollstaats" hinter sich, um eine zwei Tage dauernde Zugreise in die nördliche Metropole Chicago anzutreten. Dort hofften die Coles, wie so viele schwarze Zuwanderer aus dem Süden, eine bessere und freiere Zukunft zu finden. Vater Edward übernahm die Leitung seiner eigenen Baptistenkirche, in der die musisch veranlagte Perlina bei Gottesdiensten den Gospel-Chor leitete sowie Orgel und Klavier spielte. Die Mutter war es auch, die die musikalischen Talente der Kinder entdeckte und förderte. Schnell stellte sich heraus, dass Nat ein absolutes Gehör besaß und es scheinbar mühelos schaffte, einmal gehörte Melodien nachzuspielen.
Bei seiner Einschulungsfeier trug der kleine Nat sehr zur Gaudi seiner Mitschüler den populären Novelty-Song “Yes! We Have No Bananas” vor. Der frühe Erfolg gab ihm mächtig Auftrieb. Sein großes Vorbild war schon damals sein neun Jahre älterer Bruder Eddie, der im Gegensatz zum stillen und folgsamen Nat extrovertiert und rebellisch war. Eddie stahl sich nachts aus dem elterlichen Haus und trieb sich in den Jazzclubs der Nachbarschaft herum. Der Kirchenmusik kehrte Eddie den Rücken, um Boogie-Woogie, Blues, Jazz und populäre Schlager zu spielen. Was dem frommen und strikten Vater wiederum gar nicht gefiel – er bezeichnete all dies als “Musik des Teufels”. Muter Perlina war in der Beziehung weitaus toleranter. Für sie verkörperte Musik schlicht “das Herz der Kultur”.
Und so sorgte sie dafür, dass Nat ab dem zwölften Lebensjahr klassischen Klavierunterricht erhielt. In Eddies Fußspuren wandelnd, hing Nat nachts heimlich in der Nähe der Jazzclubs ab, die er aufgrund seines Alters nicht betreten durfte. Dort lauschte er Größen wie Louis Armstrong, Jabbo Smith, Jimmy Noone und vor allem Earl Hines, der mit seiner Band regelmäßig im Grand Terrace Ballroom auftrat. “Unsere Wohnung war nicht weit vom alten Grand Terrace”, erinnerte sich Nat später, “und manche Nacht saß ich in der Seitenstraße und hörte Earl Hines zu, um auf neue Ideen zu kommen.”
Mit fünfzehn ließ Nat die Schule sausen und widmete sich ganz der Musik. Um seinen gar nicht begeisterten Vater zu besänftigen, fuhr er zunächst zweigleisig: unter der Woche trat er bei sogenannten Rent-Partys und in Clubs als Pianist auf, während er sonntags brav in der Kirche Orgel spielte und im Chor mitsang. Allerdings ließ er sich dabei immer wieder zum Improvisieren hinreißen und wurde dann prompt von seinem Vater ermahnt, sich doch bitte zu zügeln.
Es dauerte nicht lange, bis der junge Nat in der Band von Eddie mitspielte, der inzwischen zum Bass gewechselt hatte (zwei weitere, jüngere Brüder – Ike und Freddy – machten ebenfalls Karriere als Jazzpianisten). Als Mitglied von Eddie Cole & His Solid Swingers spielte der erst 17-jährige Nat, hörbar beeinflusst von Earl Hines, 1936 erste Aufnahmen für Decca ein. Danach erhielt er einen Job als Pianist in der schwarzen Broadway-Revue “Shuffle Along”, mit der er auf eine Tournee durch die USA ging. In Los Angeles löste sich das Ensemble auf. Statt nach Chicago zurückzukehren, entschloss sich Cole in Los Angeles zu bleiben und formierte dort ein neues Quartett.
Als ihm ein festes Engagement in einem kleinen Club in Hollywood angeboten wurde, auf dessen Bühne kein Platz für ein Schlagzeug war, wurde aus der Not heraus das schlagzeuglose Nat King Cole Trio mit Gitarrist Oscar Moore und Bassist Wesley Price geboren (die später durch Irving Ashby und Johnny Miller ersetzt wurden). Mit seinem Trio landete er in den frühen 1940ern erste Hits wie “Sweet Lorraine”, “That Ain’t Right” und “All For You”. Der nationale Durchbruch gelang ihm 1944 mit “Straighten Up and Fly Right” für das neue Label Capitol Records, bei dem er sich sofort als eines der Zugpferde etablieren konnte.
Im selben Jahr nahm er zudem am ersten von Norman Granz organisierten Jazz At The Philharmonic-Konzert teil. Schon bald war Nat King Coles Name aus den Billboard-Charts nicht mehr wegzudenken. Und der brillante Pianist wandelte sich nach und nach zum erfolgreichen Crooner, der mit seiner einschmeichelnden Stimme und seinem stillen Charme ein immer größeres Publikum eroberte. Das Ende des Trios kam 1947, als Nat King Cole mit seiner Interpretation von Mel Tormés “Christmas Song” ein weiterer Mega-Hit gelang.