Наум Ихильевич Клейман родился в 1937 году в Кишинёве. Родители Н. И. Клеймана происходили из Болграда на юге Бессарабии (мать) и Романовки (отец). В годы Великой Отечественной войны — с матерью и бабушкой в эвакуации в Андижане, после освобождения города в 1946 году вся семья вернулась в Кишинёв. В 1949 году вместе с родителями депортирован в Сибирь. Учился на математическом факультете Киргизского университета во Фрунзе.
В 1961 году закончил киноведческий факультет ВГИК (мастерская Н. А. Лебедева и Е. М. Смирновой) и начал работать в Отечественном отделе Госфильмофонда. Научный консультант по реконструкции фильмов С. М. Эйзенштейна «Старое и новое» («Генеральная линия»), «Октябрь», «Броненосец „Потёмкин“». Участвовал в восстановлении в качестве фотофильма уничтоженной картины С. М. Эйзенштейна «Бежин луг» как режиссёр (совместно с С. И. Юткевичем) и научный консультант.
В 1965 году избран научным секретарём Комиссии по творческому наследию С. М. Эйзенштейна, участвовал в организации Научно-мемориального кабинета Эйзенштейна (Музея-квартиры) при Союзе кинематографистов СССР и с 1967 по 1985 год, а также с 1992 по настоящее время — его хранитель. Один из составителей и авторов комментариев «Избранные произведения Эйзенштейна» в 6 томах (1964—1971).
Заведующий музейным отделом Бюро пропаганды советского киноискусства (позже — ВТПО «Киноцентр»), директор Центрального музея кино при ВТПО «Киноцентр», с 1992 годa — директор Государственного центрального Музея кино.
C 1988 годa преподает на Высших курсах сценаристов и режиссеров (курс истории мирового кино). Вёл спецкурс по творчеству С. М. Эйзенштейна в Нью-Йоркском университете (1990 и 1991), семинар по эстетике эксцентризма и по творчеству С. М. Эйзенштейна (1994 и 1998) в Немецкой Академии кино и телевидения в Берлине, а также семинары по истории кино в Будапеште, Калькутте, Лос-Анджелесе, Мюнхене, Токио и Хельсинки.
В 1993 году избран членом Европейской Киноакадемии (EFA), получив её приз «Феликс». Награждён Орденом литературы и искусства (Франция, 1992) и медалью имени Гёте (Германия, 1995). Кавалер ордена Восходящего солнца за вклад в развитие культурных связей между Россией и Японией (Япония, 2005).
Лауреат премий Международной ассоциации кинокритиков FIPRESCI за составление ретроспективы «Неизвестное советское кино» (МКФ в Москве, 1987), имени Мела Новикова (МКФ в Сан-Франциско, 1994), имени Жана Митри (МКФ в Порденоне, Италия, 1994), Гильдии киноведов и критиков России и фестиваля «Белые Столбы» (1998).
Являлся членом международного жюри на кинофестивалях в Венеции, Берлине, Лейпциге, Торонто, Париже, Локарно, Стамбуле.
В 1993—1997 годах — автор и ведущий телевизионных программ «Музей кино», «Шедевры немого кино», «Сокровища старого кино». Автор сценария и продюсер фильма «Дом мастера» (1998). ТЭФИ присудила фильму приз «Орфей» как лучшей документальной картине 1998 года.
Брат Н. И. Клеймана — Эмануил Ихильевич Клейман — молдавский ботаник и селекционер, автор монографии «Опыт хранения плодов столового арбуза в биологических средах» (1979) и других научных трудов. Жена брата — Рита Яковлевна Клейман (урожд. Клейтман, 1947—2008) — молдавский литературовед, доктор филологических наук, специалист по творчеству Ф. М. Достоевского, заведующая кафедрой русской литературы Кишинёвского педагогического института им. И. Крянгэ и отделом иудаики Института межэтнических исследований Академии Наук Республики Молдова.
Жена — киноактриса Алевтина Алексеевна Румянцева (1929—2011).