Leben Van Cleef leistete seinen Wehrdienst im Zweiten Weltkrieg in der US-Marine auf einem Minensuchboot ab. Nach dem Krieg arbeitete er zunächst als Büroangestellter, bis er ein Engagement bei einem Tourneetheater bekam.