Urodził się w nowojorskiej dzielnicy Queens[2] jako najstarszy z trójki dzieci Helen Mary (z domu Sheedy) i Waltera Martina Frankenheimera[3], maklera giełdowego. Jego matka była irlandzką katoliczką, a ojciec niemieckim Żydem[4]. Wychowywany był w wierze katolickiej[4]. Dorastał w Nowym Jorku, gdzie od najmłodszych lat fascynował się filmem i co weekend chętnie chodził do kina. W 1947 ukończył Akademię Wojskową La Salle[5] w Oakdale na Long Island w stanie Nowy Jork, a w 1951 uzyskał maturę z języka angielskiego w Williams College w Williamstown w stanie Massachusetts, gdzie jako kapitan drużyny tenisowej rozważał karierę zawodową w tenisie[4].
W latach 1951–1953 służył w jednostce filmowej sił powietrznych USA, w randze porucznika w wojnie koreańskiej, reżyserując filmy dla armii. Po opuszczeniu jednostki filmowej USA Siły Powietrzne, Frankenheimer zapewnił sobie stanowisko asystenta reżysera w stacji CBS w Nowym Jorku[6]. Jego pierwszą pracą reżysera telewizyjnego był odcinek serialu You Are There[7] – pt. Spisek przeciwko królowi Salomonowi (1954) z Walterem Cronkite w roli narratora. W 1954 przeniósł się do Kalifornii i kontynuował współpracę z CBS, reżyserując odcinki Climax! (1955–1956) i Playhouse 90 (1956–1960). Frankenheimer zadebiutował jako reżyser w filmie fabularnym Obcy chłopiec (The Young Stranger, 1956)[8] z udziałem Kim Hunter. Jego dramat Wszystkie mu ulegają (All Fall Down, 1962) na podstawie sztuki Williama Inge’a z Eva Marie Saint i Warrenem Beatty na Festiwalu Filmowym w Cannes nominowany był do Złotej Palmy[9]. Był dwukrotnie nominowany do Złotego Globu dla najlepszego reżysera – dreszczowca Przeżyliśmy wojnę (The Manchurian Candidate, 1962) i dramatu politycznego Siedem dni w maju (Seven Days in May, 1964)[10]. W 1997 został uhonorowany Nagrodą Saturna za całokształt twórczości[9].