New York Brooklyn negyedében született, apja libanoni, anyja lengyel zsidó bevándorló volt. Zenei tehetsége gyorsan nyilvánvaló lett, nyolcévesen megkapta első (használt) zongoráját – a hangszerért anyja fél évig vállalt túlórákat. Sedaka még abban az évben felvételt nyert a híres Juilliard zeneiskola előkészítő évfolyamára, elmélyült a klasszikus zenében, de a könnyűzene sem hagyta hidegen. Tizenhárom évesen kötött barátságot a szomszédjában lakó, három évvel idősebb Howie Greenfielddel, akit ígéretes költői karrier várományosának tartottak. Együtt kezdtek dalokat írni, közös munkájuk, barátságuk Greenfield haláláig kitartott.
Sedaka középiskolásként The Tokens néven énekegyüttest alapított, amely sikerrel vette a szó szerinti slágergyárnak számító Brill Buildingben rendezett meghallgatást, majd 1956-ban megjelent első kislemezük Sedaka és Greenfield két szerzeményével. Nem lett kirobbanóan nagy siker, ezért Sedaka otthagyta a Tokenst és szólókarrierbe kezdett. Szerzeményei azonban így is lemaradtak a slágerlistákról, pedig olyan énekesek szólaltatták meg, mint például Dinah Washington.
Érettségi után ösztöndíjjal a Julliard rendes hallgatója lett, de közben gőzerővel írta Greenfielddel a dalokat. A páros 1957-ben kapott irodát a Brill Buildingben, azaz hivatalosan is fizetett slágerszerzők lettek, s nem sokkal később végre rájuk köszöntött a siker: Stupid Cupid című szerzeményük Connie Francis nagy slágere lett. Az igazi áttörés érdekében Sedaka a slágerlista éllovasait kezdte tanulmányozni, és – ahogy ezt később életrajzi könyvében megírta – ezt szűrte le: „közös vonásuk a harmonikus ritmus, az akkordok változásának pontos kiszámítása, egyfajta harmonikus fejlődés a dal csúcspontjáig, hasonló hangszerelés, háttér vokál megszólaltatása, a dob helyenként hangsúlyos szerepe és egy egyedi hangzású szólóhang”.
A receptet alkalmazva született meg 1959-ben az élete fordulópontját jelentő Oh! Carol, amelyet ifjúkori szerelmének, a később énekesként és dalszerzőként is nevet szerző Carole Kingnek ajánlott. A kislemez bekerült a slágerlisták első tíz helyezettje közé, Sedakát bemutatkozó lemezéért Grammy-díjra jelölték. Ettől kezdve ontotta a slágereket, világ körüli turnéra indult, dalait olaszul, németül, japánul és spanyolul is felvette. A Calendar Girl, a Little Devil, a Happy Birthday, Sweet Sixteen mind előkelő helyezést ért el a slágerlistákon, 1962-ben a számos feldolgozást megért Breaking Up is Hard to Do listavezető lett.
Több millió eladott lemezzel háta mögött már nemzetközi sztárnak számított, de a Beatles berobbanásával kezdődött brit invázió őt is parkolópályára tette. Alig tudott olyan dallal előállni, amely tartósan a listákon maradt volna, 1966-ban az RCA még kiadta két kislemezét, de 1967-re kiadó nélkül maradt. Munkája azonban akadt bőven: a hirdetésben összetoborzott, a Beatlesre adott amerikai válasznak szánt Monkees sikerre vitte When Love Comes Knockin' (At Your Door) című szerzeményét, sorra írta a dalokat olyan előadóknak, mint a The 5th Dimension, Tom Jones, Peggy Lee, Tony Christie.
Előadói pályafutása az 1970-es évek közepén, Angliában kezdődött újra. Új szerzeményeit tartalmazó albumai felkeltették a lemezkiadó alapításán gondolkodó Elton John figyelmét, aki Sedaka's Back címmel az Egyesült Államokban is megjelentetett egy válogatást ezekből a dalokból. A cím prófétainak bizonyult, Sedaka valóban visszatért: a Laughter in the Rain 1975-ben második listavezető dala lett, Solitaire című szerzeményét a Carpenters, a Love Will Keep Us Togethert a Captain & Tennille duó vitte sikerre, utóbbi felvétel Grammy-díjat is kapott.
Sedaka az 1990-es években képes volt ismét megújulni, lányával énekelte lemezre legszebb slágereinek duett változatát. 2007-ben fél évszázados karrierjét foglalta össze egy válogatáslemezzel, amely felkerült a Billboard sikerlistájára, ez 1980 óta nem fordult elő vele. A jubileum tiszteletére Elton John szervezett koncertet New Yorkban, a bevételt jótékonysági célokra fordították. Sedaka az elmúlt években visszatért a klasszikus zenéhez, 2010-ben a Londoni Filharmonikusokkal rögzítette első szimfonikus alkotását Életöröm címmel, valamint első zongoraversenyét.
Több mint ötven éve él feleségével, két lányuk szintén a zenei pályát választotta, fiuk forgatókönyvírással foglalkozik. Sedaka 1993 óta a zeneszerzők dicsőségcsarnokának lakója, csillaga van a hollywoodi Hírességek Sétányán, de a rock halhatatlanjai közé még nem került be, jóllehet rajongói ezt évről évre petícióban követelik.
