Naum Kleiman war Mitbegründer des namhaften Sergei-Eisenstein-Archivs, das er von 1967 bis 1985 leitete, gründete 1989 die Moskauer Cinemathek Musej Kino und übernahm ab 1992 auch deren Leitung. Seit 1988 unterrichtet er als Dozent an der New York University sowie der German Film and Television Academy Berlin und hält weltweit Vorträge. Er publizierte umfangreich zu Filmtheorie und Geschichte des sowjetischen und russischen Kinos, schrieb als Eisenstein-Spezialist zu dessen Werk und half an der Rekonstruktion seines Films Bezhin Meadow, The General Line und The Battleship "Potemkin".

Kleiman ist unteranderem FIPRESCI-Preisträger für eine Retrospektive, die er im Rahmen des Moscow International Film Festivals kuratierte, wurde 1993 zum Mitglied der European Film Academy gewählt, erhielt den "Felix" der European Film Academy und L'Ordre des Arts et des Lettres, sowie eine Goethe-Medaille. Zudem war er Jurymitglied auf Filmfestivals in Venedig, Leipzig, Toronto, Locarno und in der Berlinale. Außerdem war er langjähriger Berater und Helfer der Sektion Forum der Berlinale.