本名：ナサニエル・アダムズ・コールズ Nathaniel Adams Coles
1919年（1917年という記載あり）3月17日アラバマ州モンゴメリー生まれ。
1965年2月15日カリフォルニア州サンタモニカにて死去。
父は牧師で、母・ペリーナは教会のオルガン奏者だった。コールは12歳まで母からオルガンを習った。
1936年弟のテディ・コール（B）を加えた六重奏団でプロとして演奏活動をはじめたという記述と年は同じ1936年だが兄の
ベーシスト、エディ・コールの率いる六重奏団に加わってプロとしてのキャリアをスタートさせたという記述がある。年齢から考えて後者が正しい感じがする。
やがて彼は自分のグループを作ってシカゴに行き、レビュー団に加わった。レビュー解散後ソロ・ピアニストとしてナイト・クラブで活動を開始した。
彼はさらにニューヨークにも進出したが、ナイト・クラブ出演初日に歌を歌ったところ「こんな下手な歌はダメだ」マネージャーに怒られたという。
そこで彼はカリフォルニアに戻り、1939年にはピアノ、ギター、ベースのシンプルな編成からなる「ナット・キング・コール・トリオ」を結成して活動を始めた。
このトリオは好評で、ロスアンゼルスに来ていたベニー・グッドマン楽団に在籍していたライオネル・ハンプトンが1940年ナイト・クラブで演奏しているところを聞きに行き、
レコーディングに起用した程であった。
歌手としての彼の評価が多いが、ピアニストとしても超一流で、粟村氏などは、「ハインズ〜コール〜ウィントン・ケリー」という系譜を考えていたという。
ピアニストとしての活動の間、艶のある声を買われて、歌手としても活動するようになった。
1943年、歌手として「ストレイトン・アップ・アンド・フライ・ライト(Straighten Up and Fly Right)」を大きくヒットさせ、一躍スターの座に就いた。
その後はジャズからポピュラー界に軸足を移し、テレビにも多く出演し広く大衆的な人気を得た。
1950年以降の歌唱では、「モナ・リザ」、「スターダスト」、「ルート66」、「トゥー・ヤング」、
「ホエン・アイ・フォール・イン・ラブ」、「ネイチャー・ボーイ」などが知られる。
特に「ネイチャー・ボーイ」はミリオン・セラーとなり、人気を不動のものとした。
彼のヴォーカルの魅力は、一抹の陰りを秘めたソフトな粘り気のあるハスキー・ヴォイスにあり、
ピアノ・トリオの絶妙なスイング・フィーリングとマッチして都会的な洒落た味わいを表出した。
同じ芸風のオスカー・ピーターソンと、コールはピアノを弾かずヴォーカルに徹するから、
ピーターソンは歌を歌わずピアノに徹するという取引をしたと言われている。
この話は単なる根も葉もない都市伝説と思われていたが、実際2人はそういう話をしたという打ち明け話があり周囲を驚かせた。
それでもコールは、1956年にストレート・アヘッドなジャズアルバム「アフター・ミッドナイト(After Midnight)」を発表し、
弾き語りを行ったが、対するピーターソンもヴォーカル・アルバムを出している。
歌手としてまだ絶頂時の1965年2月15日に、カリフォルニア州サンタモニカの病院で肺癌により死去した。
1964年の「L-O-V-E」が、生前最後の大ヒット曲となった。
僕は数ある「スターダスト」の中でも彼の歌う「スターダスト」が一番好きである。
ライオネル・ハンプトンの1940年の録音に名前が見える。
「ライオネル・ハンプトン／オール・スター・セッション」(RCA RA-90〜95)
「ナット・キング・コール／イン・ザ・ビギニング」（MCA records VIM-4514）
"Lester Young／The complete Aladin recordings"(Blue note CDP 7243 8 32787 2 5)
"The King Cole trio"(ECJ-50062)
"Nat Cole at JATP"(VSP/VSPS-14)
"Dexter Gordon/Kind of Gordon"(House of jazz 220156)
"Charlie Parker/Lotusland"(Spotlite SPJ123)