Плененный этими двумя молодыми людьми со свежими взглядами на жизнь и учебу, Рудольф вдруг осознал, что его мир, до тех пор ограниченный одним балетом, необычайно расширился. В состоянии полной эйфории он вышел от новых друзей и вернулся на улицу Зодчего Росси.
Блаженство продолжилось на каникулах – студенты проводили их в Крыму, на даче хореографического училища. Рудольф держался в стороне от сокурсников. «Мы никогда не знали, где он». Он целыми днями принимал грязевые ванны или загорал на пляже. Потом произошла катастрофа. По возвращении в Ленинград его вызвали в кабинет директора и вручили следующее письмо:
«Нурееву Рудольфу Хаметовичу.
Администрация Ленинградского академического театра оперы и балета имени С. М. Кирова сообщает, что по приказу Министерства культуры Союза Советских Социалистических Республик вы направляетесь в распоряжение Министерства культуры Башкирской Автономной Социалистической Республики, куда вы должны обратиться насчет вашей будущей работы.
[подпись] И. о. директора И. Глотов».
Уфимский театр оперы и балета потребовал его возвращения: Рудольф учился в Ленинграде на республиканскую стипендию. Руководство Кировского театра согласилось его отпустить. Маргарита Алфимова вспоминает, как Рудольф выбежал из кабинета, «плача и крича». Успокаивать его пришлось Пушкину; позже он вернулся на репетицию. «Тогда я впервые увидела его в слезах, – вспоминает Алла Сизова. – Он плакал по-настоящему и говорил: «Я не могу вернуться домой. Я не могу оставить Кировский театр. Я знаю, что в балете нет ничего лучше этого театра».
Глотов написал ответ в башкирское Министерство культуры, гарантируя, что Нуреев вернется «и будет в вашем распоряжении». Однако Рудольф не собирался подчиняться. Вскоре он прилетел в Москву и отправился прямиком в Министерство культуры, где его провели в кабинет какой-то чиновницы, которая сказала, что сделать ничего нельзя: он обязан исполнить свой долг перед государством. Рудольф возражал: но ведь можно сделать исключение! В конце концов, не каждый выпускник получает предложения стать солистом сразу в трех ведущих театрах страны! «Я говорил, что они совершают большую ошибку. Я был сам себе импресарио». Чиновница сурово повторила: сделать ничего нельзя. «Да будьте вы прокляты!» – воскликнул Рудольф, выбегая из кабинета (позже он очень радовался, узнав, что на следующий день после их встречи чиновницу из-за чего-то уволили). «Я плакал на тротуаре, а потом пошел в Большой, и они меня взяли. Сказали: «Собирайте вещи, и с сентября начнете работать».
Вернувшись в Ленинград, он начал собираться и прощаться с друзьями. Но вскоре ему передали записку, в которой ему приказывали немедленно явиться в театр. Борис Александрович Фенстер, главный балетмейстер Театра имени Кирова, добродушный человек сорока с небольшим лет, поразил его, сухо сказав: «Почему вы выставляете себя таким дураком? Распаковывайтесь и оставайтесь здесь, с нами». Оказалось, что Пушкин успешно ходатайствовал за Рудольфа. Нуреева не только взяли в труппу солистом, но в ноябре 1958 г. он дебютировал с Дудинской в «Лауренсии».
Сразу после выпуска Рудольф жил в рабочем общежитии в комнате на восемь человек. Все спали на койках, привинченных к стене, как полки. Теперь, однако, он услышал, что театр выделяет ему комнату в квартире на Ординарной улице в тихом, престижном Петроградском районе. Отдельная комната была неслыханной роскошью для многих ленинградцев, привыкших к коммунальным квартирам. Однако, узнав, что он должен жить в одной квартире с Аллой Сизовой, Рудольф пришел в ярость. Встретив Нинель Кургапкину, одну из своих любимых балерин, он воскликнул: «Нет, вы слышали?! Мне дают квартиру! С Сизовой! Думают, что я рано или поздно женюсь на ней! Ни за что!!!»