В 1953 году Рудольфа пригласили в балетную студию при Башкирском театре оперы и балета. О нем уже знали как о талантливом мальчике-танцоре. Преподавала здесь Загида Бахтиярова, одна их первых балерин башкирского театра. Некоторые уроки вел главный балетмейстер театра Виктор Пяри. Студия готовила в основном артистов кордебалета, но Рудольфу доверяли и небольшие сольные партии. Он был оформлен как артист балета и получал небольшую зарплату: десять рублей за вечер. Но тогда деньги имели для Нуреева наименьшее значение: он был переполнен счастьем от того, что получил работу, и чувствовал, будто у него выросли крылья.
«В действительности же это была далеко не блестящая перспектива — все, что я делал в театре, это ходил по сцене несколько вечеров в неделю то слугой, то нищим, то римским солдатом или еще кем-то в этом роде, — спустя годы трезво посмотрит Рудольф на былые успехи. — Но исполнение этих маленьких ролей также требовало репетиций, и становилось все труднее и труднее пропускать уроки и удерживаться в школе. Даже более юные, чем я, когда решали идти зарабатывать себе на жизнь, просто заявляли об этом своим родителям, и те устраивали их для продолжения учебы в вечернюю школу. Но как я мог признаться, что зарабатываю всего 300 рублей в месяц? Наконец, представившись артистом Уфимского оперного театра, я побывал в различных рабочих коллективах, где предлагал давать еженедельные уроки народного танца за 200 руб. в месяц. Это требовало большого нервного напряжения, но я понял, что могу заниматься этим. Так или иначе, но я стал зарабатывать столько же, сколько зарабатывал мой отец в те дни. Обстоятельства складывались благоприятно».
Со временем обстановка в семье Нуреевых немного смягчилась: статус театрального артиста значил немало. Правда, десятый класс Рудик заканчивал уже в школе рабочей молодежи — учиться в обычной школе и работать оказалось непросто.
У Рудольфа появилось еще одно увлечение, сохранившееся на всю жизнь: живопись. Вместе с другом Альбертом Арслановым он коллекционировал репродукции картин. Юноши тайно откладывали деньги, чтобы отправиться в Москву и своими глазами увидеть подлинники любимых произведений. В 1954-м им удалось съездить туда на автобусе — из Рязани, где оба были на гастролях вместе с театром. По залам Третьяковки бродили до самого закрытия, забыв про еду и про все на свете.
В 1955 году Башкирская республика отбирала танцовщиков для участия в таком важном событии, как декада башкирского искусства — она проходила в Москве.
Наступил день, когда артисты балета Башкирского оперного театра должны были предстать перед комиссией, которая отбирала артистов для участия в декаде. Все было готово: и артисты, и члены комиссии, за одним исключением. Один из солистов балета отсутствовал по невыясненной причине. Тогда директор театра поднялся на сцену, созвал всех артистов и объяснил сложившееся положение. Он спросил, нет ли желающих выступить в этой партии, чтобы просмотр мог продолжиться.
Рудольфу все происходящее показалось фантастическим сном. Он машинально поднял руку и выступил вперед. Затем, после короткого занятия с балетмейстером, вышел на сцену и станцевал… Победа оказалась полной: его включили в программу конкурса!
Но в столице произошло непредвиденное. То ли по причине усталости и радостного возбуждения, то ли из-за того, что юный конкурсант еще не привык к обычному нормальному режиму взрослых артистов балета и к изнуряющему ритму их работы (только в день приезда прошло три репетиции!), он, неудачно приземлившись после пируэта, растянул связки на пальце ноги. Ступня Рудика вскоре так распухла, что он не смог даже надеть туфли и должен был оставаться в балетных тапочках.
Аккомпаниатор Ирина Воронина, которая по-прежнему покровительствовала Рудику, сделала все возможное, чтобы в столице заметили ее любимого ученика.
Через неделю, когда палец юноши уже зажил, по рекомендации Ирины Александровны Рудик отправился в класс знаменитого Асафа Мессерера, танцовщика Большого театра и одного из известнейших педагогов, занятия которого ежедневно посещали звезды советского балета, включая Галину Уланову. Мессерер попросил Рудика подождать, пока он закончит урок, и разрешил ему присутствовать в классе. Но в конце урока Мессерера вызвали по какому-то срочному делу, и в класс он не вернулся. Рудик готов был заплакать от огорчения. Следующий день оказался удачнее: проэкзаменовать молодого солиста из Башкирии поручили другому педагогу. В конце экзамена он сказал, что если Нуреев решит поступить в Московскую балетную школу, то, скорее всего, попадет сразу в 8-й класс, поскольку элементарные основы хореографии ему уже известны.