Tam przez trzy lata kształcił się pod okiem legendarnego mistrza Aleksandra I. Puszkina. Ambitny artysta zachwycał publiczność na występach w ogólnokrajowym konkursie w stolicy, jak i w przedstawieniu dyplomowym w swojej szkole, po którym objął stanowisko solisty w Teatrze im. Kirowa. Podczas trzyletnich występów w balecie wykonywał pas de quatre w balecie Raymonda, pas de deux w Śpiącej Królewnie, pas de trois w balecie Jezioro łabędzie. Występował również w klasycznych przedstawieniach jak: Don Kichot, Dziadek do orzechów, Giselle. Podczas swoich występów w Teatrze Kirowa Nuriejew przejawiał predyspozycje do tworzenia własnych interpretacji i inwencji twórczej. Ze względu na olbrzymią popularność jego życie osobiste, jak i działalność artystyczna znalazły się w kręgu zainteresowań radzieckich służb bezpieczeństwa (KGB). mały|227x227px|Nuriejew i Margot Fonteyn (1968) Mimo to w 1961 Nuriejew otrzymał szansę wystąpienia przed francuską widownią. Pierwszy występ radzieckiej grupy baletowej w Paryżu, z którą Nuriejew tam przybył, odbył się 1 czerwca. Podczas pobytu, ciekawy świata Nuriejew, dzięki dobrej znajomości francuskiego, zawarł znajomości z kilkoma Francuzami, głównie tancerzami, co spotkało się z zarzutami ze strony opiekującego się grupą agenta KGB.