ニューヨーク州ニューヨーク市生まれ。マンハッタン育ち。父はロシア系、母はリトアニア系の移民で両方ともユダヤ系^[1][2][3]。父親が家族を捨てたため、貧しいローワー・イースト・サイドのアパートに移り、母親は繊維業界で働き、ウォルターも新聞配達などをして家計を助けた^[4]。コロンビア大学でジャーナリズムを学び、第二次世界大戦中は空軍に従軍した。

除隊後に演技を学んで舞台で活躍し、1955年、バート・ランカスター監督・主演の西部劇『ケンタッキー人』で映画デビュー。ジャック・レモンと組んだコメディ映画や刑事物などのアクション作品が有名である。1966年の『恋人よ帰れ!わが胸に』でアカデミー助演男優賞を受賞した。

1959年に女優のキャロル・グレイス（英語版）と結婚し、一人息子のチャールズは映画監督になり、息子の作品に出演したこともある^[4]。