[[Fitxer:Phoebe Cates 3.jpg|thumb|left|Kline i la seva esposa Phoebe Cates, 1989]]
AlEl 1976, Kline abandonà The Acting Company i s'establí a Nova York, on interpretà una breu temporada el personatge de ''Woody Reed'' a la comèdia televisiva ''[[Search for Tomorrow]]''. Tornà als escenaris al 1978 amb el petit paper de "Bruce Granit", una caricatura d'ídol de matinée a la versió de [[Harold Prince]] de ''[[On the Twentieth Century]]'', amb el qual guanyà el seu primer [[Premi Tony]].<ref name="parents"/> El 1981, Kline va aparèixer amb la diva de rock [[Linda Ronstadt]] i el cantant [[Rex Smith]] a la producció del New York Shakespeare Festival's Central Park de ''[[The Pirates of Penzance]]'', guanyant un segon Premi Tony, aquest cop com a [[Premi Tony al Millor Actor Protagonista de Musical|Millor Actor en un Musical]], per la seva còmica interpretació del Pirata Rei. El 1983 el tornà a interpretar a la [[The Pirates of Penzance (pel·lícula de 1983)|versió fílmica del musical]], de nou amb Ronstadt, Smith i amb [[Angela Lansbury]], que tingué una tèbia acollida.<ref name="parents"/>
El 1982, després que el crític [[Frank Rich]] del ''[[New York Times]]'' l'anomenés ''l'Olivier americà'' pel seu treball escènic, Kline s'aventurà al cinema al 1982 a ''[[La decisió de la Sophie]]'', d'[[Alan J. Pakula]]. Interpretà el cobejat paper del turmentat i mercurial Nathan, oposat a [[Meryl Streep]]. Steep guanyà el [[Oscar a la millor actriu|Premi Oscar]] per la seva actuació, mentre que Kline va ser nominat al [[Globus d'Or]] i al [[Premi BAFTA]] per la millor actuació debutant.
