Седака написал эту песню с поэтом-песенником Ховардом Гринфилдом (они знали друг друга с детства и работали вместе на протяжении многих лет)[1].
По утверждению сайта Songfacts, песня была названа в честь сонграйтера Кэрол Кинг (имя при рождении Кэрол Кляйн), которую Седака знал с тех пор, как та была в его самой первой группе Linc-Tones (которую он сформировал, окончив школу). При этом в реальности они никогда не были парнем и девушкой и на свидания друг с другом не ходили[1]. В ответ она записала песню «Oh! Neil», но успеха в хит-параде не имела.
По одной из известных версий, продюсер Дон Киршнер, давний друг Седаки, тогда работавший в музыкальном издательстве Aldon Music, посоветовал певцу:
Напиши песню с именем девушки в названии. В середине песни разговаривай, как это сделали The Diamonds в [песне] „Little Darling“.
Эта песня стала первым хитом Седаки, попавшим в первую десятку в США. (А первой песней, попавшей в США в чарты, была песня «The Diary», которая добралась до 14 места в 1958 году.)[1]