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. Auf einer dieser Vorstellungen wurde er von Stanley Kramer entdeckt, der ihn für die Nebenrolle des Jack Colby in Zwölf Uhr mittags engagierte.
Obwohl es sich nicht um eine Sprechrolle handelte, brachte ihm seine unverwechselbare Physiognomie mit den scharfgeschnittenen Zügen und der Adlernase einen großen Bekanntheitsgrad ein. Van Cleef spielte, nachdem er in Zwölf Uhr mittags in diesem Rollenfach sehr effektiv gewesen war, in mehreren Westernklassikern den unrasierten, verschlagenen Helfershelfer des Hauptschurken (etwa in Der Mann, der Liberty Valance erschoß). Er übernahm zahlreiche Rollen in Kriminalfilmen und Fernsehserien wie Bonanza, Am Fuß der blauen Berge, Maverick oder Tausend Meilen Staub, ohne dabei Starruhm zu erreichen.
Mitte der 1960er Jahre arbeitete Van Cleef fast ausschließlich für das Fernsehen, als ihn Sergio Leone für die Hauptrolle des Colonel Mortimer in Für ein paar Dollar mehr engagierte, den zweiten Teil der Trilogie mit Clint Eastwood.
Hierbei wurde er mit Klaus Kinski bekannt, der sich aufgrund einer für ihn demütigenden Streichholzszene im Film nie mit Van Cleef anfreunden konnte.
In Zwei glorreiche Halunken, dem letzten Teil der Trilogie, spielte Van Cleef die Rolle des Bösewichtes Sentenza. Beide Filme gelten heute als Klassiker des Italowesterns. Seine Karriere war dadurch wieder in Schwung gekommen, er etablierte sich als einer der populärsten Stars des Italowesterns und spielte meist abgebrühte, überlegene Kopfgeldjäger oder desillusionierte Revolverhelden – oftmals in ungewollter Rolle als Vaterersatz für junge Cowboys am Rande der Gesellschaft (Der Tod ritt dienstags, Die Rechnung wird mit Blei bezahlt, Der Gehetzte der Sierra Madre, Drei Vaterunser für vier Halunken). Ein großer Erfolg wurde auch die von ihm in zwei Filmen interpretierte Figur des Sabata. Seine Darstellung war so stilprägend, dass ihm die Figur des Kopfgeldjägers in dem gleichnamigen Lucky-Luke-Comic sowie die Figur Cad Bane in der Serie Star Wars: The Clone Wars nachempfunden wurden.
Als die Popularität der Italowestern nachließ, kehrte Van Cleef in den frühen 1970er Jahren in die USA zurück, konnte dort aber, im Gegensatz zu Charles Bronson oder Clint Eastwood, nicht mehr an frühere Erfolge anknüpfen. Fast alle Filme, die er ab den 1970er Jahren drehte, waren zweitklassige Billigproduktionen.
Van Cleef war dreimal verheiratet: ab 1943 mit Patsy Ruth, 1960 ließen sie sich scheiden. Im selben Jahr ehelichte er Joan Drane, 1974 folgte die Scheidung. 1976 heiratete er Barbara Havelone, die Ehe hielt bis zu seinem Tod 1989. Van Cleef hinterließ vier Kinder.