Colaborarea cu "Panama", începută în perioada în care Nat nu împlinise încă 18 ani, a dus la două mari rezultate.
Primul a fost reprezentat de contractul cu casa de discuri Decca, unde a înregistrat piesele "Honey Hush", "Thunder", "Bedtime" şi "Stompin' at the Panama", şi cel de-al doilea rezultat, întâlnirea cu dansatoarea Nadine Robinson.
La finele contractului, Nat şi Nadine s-au alăturat unui grup de muzicanţi numit "Shuffle Along" şi au pornit în turneu cu ei. În 1938, Nat şi Nadine (care era cu zece ani mai în vârstă decât el) s-au căsătorit. După spectacolul din Los Angeles, susţinut de trupă, Nat şi-a petrecut o bună parte din timp cântând la un pian aproape stricat.
Cu toate acestea, stilul său a fost remarcat la scurt timp de Bob Lewis, managerul unui club de noapte numit "The Swanee Inn". Barul i-a adus lui Cole primele mari succese, dar şi nickname-ul de "Rege", sau "Regele Cole".
NUMĂRUL UNU
Nat împreună cu chitaristul Oscar Moore şi cu basistul Wesley Prince au debutat în toamna anului 1938 sub titulatura "King Cole Swingsters". Apoi, formaţia şi-a schimbat numele în "King Cole Trio". În septembrie 1938, grupul a făcut primele transcrieri radiofonice. Iniţial, acestea nu au fost destinate lansării comerciale. În 1931 şi 1940 au făcut înregistrări ocazionale pentru mărci mai puţin reprezentative.
La sfârşitul anilor '40 a apărut primul contract cu Decca Records, iar piesa "That Ain't Right" a ajuns numărul unu în topul revistei Billboard, Harlem Hit Parade. În aceeaşi perioadă, Wesley Price părăseşte grupul şi va fi înlocuit de Johnny Miller. Următorul single al trioului, "All for You", a fost înregistrat sub marca Excelsior în octombrie 1942, deoarece contractul cu Decca expirase chiar înaintea ascensiunii piesei "That Ain't Right". Imediat după lansare, "All for You" a fost cumpărată de Capitol Records şi reeditată. La 20 noiembrie 1943, piesa a ajuns din nou pe primul loc în topul Harlem Hit Parade.
Ulterior, Capitol a semnat contractul cu Cole urmând piese ca "Straighten Up and fly Right" (numărul unu în topul muzicii de culoare) şi "Gee baby, Ain't Good to You".
Albumul de debut al trioului, lansat sub sigla Capitol Records, intitulat "The King Cole Trio", a apărut în toamna anului 1944 cu un conţinut de opt titluri, dintre care doar trei cu vocea lui Cole. În momentul în care a luat naştere primul top Billboard al albumelor, la 24 martie 1945, "The King Cole Trio" a ajuns numărul unu. Timp de 12 săptămâni şi-a păstrat poziţia fruntaşă.
ŞCOALA DE MUZICĂ
Încă de la început, Cole a fost extrem de pasionat de istoria muzicii. Studiul l-a determinat să pătrundă mai adânc în... mrejele ei şi să descopere tot ce ţine de acest domeniu fascinant. Revista Ebony publicase un material în care dezvăluia că "în istoria modernă a muzicii americane au existat trei clase majore. Cea mai veche a fost considerată Şcoala de muzică Napoletană, rezultată din fuziunea stilurilor lui Al Jolson's şi Carlo Buti, cu lideri precum Harry Lillis «Bing» Crosby, Buddy Clark, Perry Como, Dean Martin şi Elvis Presley.
Cea de-a doua şcoală, Big Band, a pornit de la megafonul lui Rudy Valley's şi primul microfon fără fir cu care au cântat Bob şi Ray Eberly, Frank Sinatra, Vic Damone, Steve Lawrence şi Jack Jones. Cea mai nouă şcoală de muzică este Cool School, care a pornit de la tonul grav şi gros al lui Louis Armstrong, Jimmy Rushing sau Louis Prima, şi a culminat în tonul cald şi plăcut al lui Nat King Cole". Stilul lui Cole a fost adoptat mai târziu de o serie de artişti precum Mel Torme, Johnny Ray, Johnny Mathis, Oscar Peterson Frankie Laine, Tony Bennett etc.
ARTA PERCEPŢIEI
Performanţele sale în muzică s-au datorat şi faptului că Nat King Cole nu a greşit niciodată ritmul unui cântec. Sensibilitatea timbrului şi a texturii vocale i-au transformat muzica în artă. Chiar şi Frank Sinatra i-a admirat întotdeauna intonaţia. Nat King Cole nu se ghida după note. Nu de fiecare dată îşi învăţa partitura, şi cu toate astea reuşea să pună accent pe vocale şi să dea drumul consoanelor... ca la carte.
Era un maestru al "artei percepţiei". Vocea de catifea, aşa cum a fost numit, ştia să acopere cu lejeritate orice parte a unei piese, acordând astfel o notă dramatică foarte importantă pentru sunetul muzicii.
Nat King Cole a fost unul dintre puţinii artişti care au stăpânit foarte bine arta rubato (termen muzical care se referă la capacitatea de a ridica vocea în ritm rapid şi apoi de a o coborî foarte încet). De aceea, abilităţile sale de narator au fost uşor de sesizat, iar lirismul din interpretare se confunda cu o naraţiune.
Artistul, atras de jazz, a devenit un "profesor" al baladelor, predecesorul folkului de astăzi... trubadurul american.