Nathaniel Adams Coles nasceu no dia 17 de março de 1919, em Montgomery (Alabama, EUA). Filho duma família pobre, mas apaixonada pela música, muito cedo aprendeu a tocar piano, apoiado pela mãe. Em 1923, a família mudou-se para Chicago.
Em 1931, já tocava órgão e cantava na igreja onde o pai pregava. Cole foi bastante influenciado por Earl Hines, o pianista mais famoso de Chicago. As suas primeiras gravações foram, em 1936, quando fazia parte da banda do irmão Eddie, contrabaixista. Nesse ano, mudou-se para Los Angeles.
Em 1937, formou The King Cole Trio com o guitarrista Oscar Moore e o baixista Wesley Prince, tornando-se músicos tornando-se residentes do clube Swanne Inn(Hollywood). O mais curioso é que esse grupo não tinha um baterista e o próprio conceito de trio de jazz foi praticamente estabelecido por este formato.
Em 1943, Cole gravou "Straighten Up And Fly Right", o primeiro solo vocal com o seu trio, que se tornou num sucesso, a nível nacional. O sucesso foi aumentando e osa espetáculos com o seu trio foram reduzindo. Nesse ano, chegou ao topo do "rhythm & blue", com duas músicas: "That Ain't Right" e "All for You".
Em 1946, lançou "(I Love You) For Sentimental Reasons", que chegou ao topo da música pop. A canção "The Christmas Song" foi gravada com uma orquestra e tornou-se um clássico da época natalícia.
Cole rivalizava em sucesso com o seu contemporâneo Frank Sinatra, pois dezenas de músicas que caíram no gosto popular, algo extraordinário para um artista negro em pleno período de discriminação racial. Cole chegou a apresentar-se para públicos brancos e negros separadamente.
O cantor foi um dos primeiros negros a ter um programa semanal na rádio e, no princípio dos anos 50, já era internacionalmente famoso. Em 1956, começou a fazer um programa semanal na televisão norte-americana, mas acabou porque os patrocinadores não queriam os produtos associados a um homem negro.
Foi um dos primeiros negros a ter um programa semanal na rádio e, no princípio dos anos 50, já era internacionalmente famoso.
Cole também participou nalguns filmes: "Cat Balou", "Blue Gardenia" e "St Louis Blues" (1958) - ficção sobre a vida de W. C. Handy. Cole acumulou um grande número de sucessos, cantando também em espanhol e português. Nesta língua, ficou marcada a sua interpretação de “Não Tenho Lágrimas”, de Max Bulhões e Milton de Oliveira.
Pelo seu hábito de fumar diariamente três maços de cigarro, Cole acabou a sua carreira muito cedo, por causa dum cancro na garganta. Apesar de se ter tornado mundialmente famoso com o seu canto, foi no piano e com o seu trio que influenciou o mundo do Jazz.
Em 1991, a sua filha, a cantora Natalie Cole, lançou o álbum "Unforgettable With Love", utilizando uma nova tecnologia que permitiu gravar duetos com o pai, usando velhos registos musicais. O álbum manteve-se no primeiro lugar nos tops, durante 5 semanas, tendo ganho o prémio Grammy de Melhor Álbum do Ano.