Az egész 1945 forró nyarán kezdődött, amikor a zongorista Mel Tormé és a szövegíró Bob Wells épp egy zenés filmhez írtak közösen zenét. A hőségben a hidegre szerettek volna gondolni, így született meg mindössze 45 perc alatt egy improvizált dallamból és gyors szövegötletből a The Christmas Song. Egy évvel később Tormé meglátogatta Nat King Cole-t annak Los Angeles-i otthonában, és felajánlotta neki a szerzeményét. Ekkor már Cole pályája felfelé ívelt, de a faji megkülönböztetés miatt még sok rádió nem volt hajlandó játszani a dalait. Cole-t nagyon megragadta a dal, és rohant, hogy meghangszerelje. Félt, hogy népszerű kortársai, Bing Crosby vagy Dinah Shore megelőzik őt a feldolgozásban. 1946 júliusában és augusztusában két verziót is rögzített belőle: az elsőt triójával, ami csak 1989-ben látott napvilágot, a másodikat pedig vonósokkal. Nat King Cole az első perctől fogva érezte, hogy a The Christmas Song igazi karácsonyi sláger lehet, és lebonthatja a szegregációs korlátokat. Megkereste hát a dallal a Capital Recordsot, akik először elutasították őt, nem bízva abban, hogy az emberek egy fekete művésztől szeretnének karácsonyi dallamot hallgatni.

Az emberek pedig újabb slágerre vágytak a királytól. Ez győzte meg a Capital Records vezetőit, hogy kiadják a The Christmas Songot. Az időzítés tehát nem is lehetett volna jobb. Cole 1961-ben még egyszer rögzítette a dalt, immár kifinomultabb, szimfonikus hangszerelésben, ez a verzió a mai napig az egyik legnépszerűbb ünnepi sláger.