Очень скоро из героя-однодневки Нуриев превратился в настоящую звезду. Публика воистину сходила с ума. Попасть на спектакль с участием дуэта Фонтейн — Нуриев было просто невозможно. По воспоминаниям одного из сотрудников концертного бюро, устраивавшего гастроли Королевского балета в Америке, это была настоящая истерия. Люди разбивали палатки возле здания «Метрополитен-опера» и дежурили по трое суток, чтобы достать билеты.
Посмотреть на Нуриева приходили Грета Гарбо и Жаклин Кеннеди. Марлен Дитрих откровенно с ним флиртовала. Джон Персиваль, балетный критик Times, сказал о Фонтейн и Нуриеве: «Партнерство, подобное этому, мы никогда не видели раньше и не увидим вновь. Уникальные и сверкающие таланты, каждый самостоятельно превосходен и очень отличен от другого, соединились вместе, чтобы создать еще более великое».
О Нуриеве вполне справедливо писали впоследствии, что в его исполнении были свои недостатки. Однако мужской танец становился не только равноправным с женским, но ив исполнении Нуриева обретал самостоятельное значение, наполненный не меньшей красотой и выразительностью. Он показываой на балетной сцене красивое мужское тело, не боясь его обнажать и умело используя грим. Многим притягательность Нуриева казалась волшебной, магической. Большой эффект производила на зрителей его экзотическая внешность с резкими, восточными чертами лица, экспрессивная, выразительная пластика, а самое главное — неугасимый внутренний огонь, который был виден в каждом его движении и жесте.
Но премьера «Жизели» принесла Нуриеву и огорчение: Эрик Брюн приревновал его к роли. Ранее он сам танцевал Альберта и был прекрасным Альбертом — но не таким, как Нуриев.
Шесть лет назад, танцуя в паре со стареющей примой Алисией Марковой (англичанкой из труппы Дягилева, взявшей русский псевдоним), он ошеломил мир балета, покорив публику безупречной техникой — но он не внес новизны в образ героя. Успех был бурным — но не таким бурным, как сейчас у Нуриева. И никогда на его долю не выпадало таких оваций. Эрик бросился вон из театра, Нуриев за ним, а следом ринулись восторженные поклонницы. Это была их первая размолвка — потом таких будет еще много. Постоянная ревность, соперничество, ссоры, примирения — и неприходящая потребность друг в друге.
Трудности в их отношениях усугубились после того, как всевластная Нинет де Валуа заключила годичный контракт с Нуриевым, отвергнув Эрика Брюна. Тот действительно потерял уверенность в себе: спокойному уравновешенному датчанину было невозможно выдержать сравнение с необузданным татарским темпераментом Нуриева, которого позднее назовут «Чингисханом сцены». Понимая это, Эрик замкнулся в себе, его манера сделалась схематичной, лишенной души, разладилось взаимопонимание с партнершей.
Обиженный и разозленный Эрик Брюн вернулся в Копенгаген. Там он пробыл недолго, а Руди звонил ему каждый день. Потом приехал навестить. И тут в довершение бед у Эрика Брюна скоропостижно умерла мать, которую он очень любил. Рудольф, разлученный со своей матерью, искренне сочувствовал ему в его горе.
Но вместе они пробыли недолго: Брюн заключил контракт с Сиднейской оперой. Рудольф Нуриев очень тосковал по нему и поначалу звонил ежедневно — а Эрик не желал с ним говорить. Улаживала конфликт чудесная женщина, балерина, бывшая невеста Эрика Соня Арова, искренне полюбившая обоих. Она подолгу объясняла Рудольфу, что далеко не всем людям нужно, как ему, выплеснуть свои проблемы на других. Что некоторые предпочитают замыкаться в себе и переживать все молча. Рудольф понимал. ине понимал. Желая объясниться, он взял отпуск и сам отправился в Сидней. Надо заметить, что Рудольф Нуриев, много гастролировавший и облетевший весь земной шар, несмотря на это, страдал аэрофобией и летать очень боялся. Но тут желание встретиться с любимым человеком пересилило страх. Однако во время полета произошел инцидент, который сам Нуриев вспоминал с ужасом.
Самолет приземлился в Каире для дозаправки, но почему-то пилоты медлили с вылетом. Потом вдруг пассажиров попросили покинуть самолет. Нуриев напрягся: он был убежден, что за ним охотится КГБ и что имеется приказ его похитить или искалечить. Поэтому он отказался покидать салон самолета и бросился к стюардессам, умоляя их спрятать его. Одна из девушек ему поверила. Она втолкнула танцовщика в кабинку туалета и повесила на дверях табличку «Out of order» — «Не работает». А к самолету уже направлялись двое в серых костюмах. Они долго обыскивали салон, стучали в дверь туалета, дергали за ручку. потом удалились ни с чем. Все это время Нуриев стоял не двигаясь и затаив дыхание. Он смотрел на себя в зеркало и видел, как седеет.
Он рассказывал об этом происшествии много раз, некоторые верили и сочувствовали беглому танцовщику, другие приписывали все его чрезмерной мнительности. Но факт остается фактом: случаи внезапного таинственного исчезновения перебежчиков из СССР в те годы были нередки.