Sau khi tốt nghiệp trường trung học Abraham Lincoln, Sedaka và một số bạn cùng lớp của mình thành lập một ban nhạc có tên là Linc-Tones. Ban nhạc đã có hit khu vực nhỏ với các bài hát như "While I Dream", "I Love My Baby", "Come Back, Joe", và "Don't Go", trước khi Sedaka bắt đầu sự nghiệp solo của mình và rời khỏi nhóm vào năm 1957.