Когда Рудику исполнилось десять лет, он поднялся на новый уровень — его приняли в танцевальный кружок при Дворце пионеров. Дом пионеров и школьников в Уфе был открыт в 1936 году. До Великой Отечественной войны он располагался в доме № 61 по ул. Зенцова, переименованной в 1937 году в ул. Ленина. В его многочисленных кружках занимались более тысячи воспитанников. Огромный вклад в развитие танцевального искусства в Уфе внес балетный кружок. Кружок танца вела Анна Ивановна Удальцова, профессиональная танцовщица, выступавшая некогда в кордебалете у Дягилева. А надо сказать, что Дягилев даже в кордебалет плохих танцовщиков не брал. Потом она вышла замуж за белого офицера, он попал в тюрьму, а после его освобождения их обоих сослали в Уфу. В свою студию Удальцова принимала далеко не всех. Прежде всего она потребовала, чтобы Рудик продемонстрировал ей, что уже умеет. Он станцевал гопак и лезгинку — Удальцова была поражена и очарована.
Тогда ей было чуть более шестидесяти лет, это далеко еще не старость, но выглядела она на все семьдесят: сказывались жизненные невзгоды. К счастью, жизнь забрала у Анны Ивановны лишь красоту, пощадив ее здоровье: первая учительница Рудольфа Нуриева дожила до ста трех лет и умерла в один год со своим прославленным учеником. В 1989-м, когда Нуриеву разрешили вернуться в СССР и посетить Уфу, они встретились. Глаза Анны Удальцовой светились искренней радостью. Она обнимала и целовала своего ученика, живо интересуясь его выступлениями. По воспоминаниям друзей, Удальцова всегда была очень добрым человеком, но в то же время ей был свойственен определенный снобизм: она относилась к маленькому Рудику хоть и ласково, но все же с пренебрежением, порой называя его «неумытым татарчонком».
Нельзя утверждать, что Нуриеву все давалось легко. Напротив! Он был слабым мальчиком: сказалась его нелюбовь к играм на свежем воздухе и порой диковатым забавам мальчишек. Так, когда преподаватель велел развести в стороны прямые руки и так делать упражнения, то Рудик долго не выдерживал такой позы, сгибая руки в локтях и поджимая пальцы. Впоследствии у него уйдут долгие часы упражнений на то, чтобы наработать мышечную массу и закалить свое тело.
Прозанимавшись с Рудиком некоторое время, Удальцова заключила: ему необходимо ехать в Ленинград, или как она привыкла называть этот город — в Санкт-Петербург. Только там он получит желаемое образование, только там его научат мастерству классического танца. Удальцова знала, о чем говорит: в Ленинграде жила ее дочь, и старая балерина каждый год ездила ее навестить и обязательно посещала Мариинку — Кировский театр.
Удальцова дала Рудольфу первые уроки классического танца, а в 1953-м при театре открылась уже настоящая балетная студия, где преподавали вышедшие на пенсию солисты Уфимского театра оперы и балета. Нуриев перешел в класс бывшей балерины Мариинского театра Елены Константиновны Войтович. Уважение к ней он сохранил на всю жизнь.
Другим его преподавателем стала Загида Нуриевна Бахтиярова — ранее блиставшая на сцене Уфимского театра. Занималась с ним и Зайтуна Насреддинова, некогда поразившая его грацией и красотой в «Журавлиной песне». Брал он уроки и у ее мужа — Халяфа Гатеевича Сафиуллина, блестящего танцовщика, прославившего башкирский балет. Учителя понимали его, разделяли его идеалы, поощряли его усилия, а дома продолжалось противоборство с отцом. Рудольф уже окончил среднюю школу. Его ровесники работали или учились, приобретая нужную профессию, а он упорно не хотел этого делать, продолжая выступать с танцевальными коллективами Уфы. Бестолковость сына злила и раздражала Хамета. Он постоянно бранил сына и жену — за то, что потакала оболтусу. До конца жизни этот человек так и не понял, что артист балета — это завидная и почетная профессия, продолжая считать сына неудачником. Он не мог оценить адский труд, благодаря которому дается легкость балетных движений, называя Рудольфа лодырем и лентяем.
Обстановка в семье стала более мирной, когда Рудольф получил место статиста в труппе Уфимского театра оперы и балета и принес домой первую зарплату.
