Su primera película como director fue El día 25, el primer día (1968), en la que compartía los
créditos como director con Arkadii Tyurin. La película era una conmemoración de la Revolución de Octubre, en la que se utilizaban obras de los artistas soviéticos revolucionarios Petrov-Vodkin y Altman.
Su siguiente película fue La batalla de Kerzhents (1971), codirigida con Ivan Ivanov-Vano, a cuyas órdenes Norshteyn ya había trabajado anteriormente. La película trata de la resistencia de los rusos ante la invasión tártara, y en ella utiliza varias imágenes medievales (frescos, miniaturas, iconos, etc). Fue un éxito internacional, y obtuvo el máximo galardón del Festival de Zagreb de 1972.
Durante los años setenta, continuó trabajando como animador en varias películas, como El zorro y la liebre (1973), La garza y la grulla (1974) y El erizo en la niebla (1975). Su obra más reconocida, sin embargo, llegó en 1979: El cuento de los cuentos. Esta película, de 27 minutos de duración, no tiene un argumento convencional, sino que se basa en asociaciones mentales.
Para sus películas de animación, Norshteyn utilizó una técnica especial, consistente en emplear varias láminas de vidrio para dar un aspecto tridimensional. Nunca ha querido utilizar ordenadores en su obra. Durante muchos años ha colaborado con su esposa, la artista Franchesca Yarbusova, y con el cineasta Alexandr Zhukovsky.
Obtuvo varios premios en los años setenta y comienzos de los ochenta. Sin embargo, en 1985 fue despedido de Soyuzmultfilm por trabajar demasiado lentamente en su última película, aún no terminada, que será presumiblemente un largometraje basado en la obra de Gogol El abrigo. Cuando fue despedido, después de dos años de trabajo, había logrado terminar diez minutos de película.
En abril de 1993 y otros tres destacados animadores rusos (Fyodor Khitruk, Andrey Khryanovsky, y Edward Nazarov) fundaron la Escuela y Estudio de Animación (SHAR Studio) en Rusia. Actualmente, Norshteyn trabaja aún en El abrigo, proyecto que ha tenido varios problemas financieros.