Французский импресарио Жорж Сориа проконсультировался с министром культуры Екатериной Фурцевой. Та подтвердила: «Да, он чудо, но с ним были проблемы». Французы настояли не только на том, чтобы Рудольфа отправили на гастроли, но и потребовали, чтобы Сергеев и Дудинская передали свои партии более молодым членам труппы и ехали только в статусе «художественных руководителей». «Мы напоминали, что они составили славу театра и должны ее хранить. Вполне понятно, они очень разозлились – для них наше решение стало тяжким ударом, – но выбора у них не было». С таким решением Рудольф согласился от всего сердца – по крайней мере, в том, что касалось Сергеева. Он сам говорил примерно то же самое, когда подошел к Сергееву и Дудинской после спектакля и прямо объявил: «Наталия Михайловна, вы были чудесны и должны танцевать еще много лет, но Константину Михайловичу пора уходить». Рудольф не скрывал своего презрения к исполнению Сергеева. Его «Жизель», по словам критиков, «не столько далека от традиций Сергеева, сколько откровенно бросает им вызов». «Ему не нравился его стиль, – подтверждает Ирина Колпакова. – Я всегда ходила на «Жизель», когда выступали Дудинская и Сергеев, а Рудик – никогда. Ему было неинтересно». В начале 1961 г., после неожиданной смерти Бориса Фенстера, главным балетмейстером театра назначили Сергеева, и Рудольф пришел в ужас. На руководящей должности Сергеев был настоящим консерватором и сохранял консервативный подход к репертуару – именно поэтому хореограф Леонид Якобсон в середине 1950-х призывал убрать его с этого поста. В то время как прогрессивный Фенстер всегда поддерживал Нуреева, Сергеев на каждом шагу чинил ему препятствия. Поэтому Рудольф очень удивился, узнав, что его включили в список танцоров, которые поедут в Париж: «Очень странно, что я обязан [этим шансом] человеку, который, как мне казалось, всегда был настроен против меня». Только гораздо позже он выяснил, что его отстояла Жанин Ринге, которую он тогда совершенно не знал. Он не мог предвидеть и того, что Сергеев неожиданно станет его союзником, когда представится возможность для политического маневрирования.
Юрий Григорович, 34-летний хореограф, чью первую постановку, «Каменный цветок», сочли революционным отходом от шаблонных драмбалетов, очень распространенных в советских театрах, приступил к очередной масштабной постановке и увидел в восточной пластике и романтической внешности Рудольфа именно те качества, которые требовались для его героя. Григорович был репетитором Рудольфа в «Жизели» и с тех пор стал его поклонником и защитником, находя, что его новаторская манера исполнения близка по духу к тому, что он внедрял в хореографии. В «Легенде о любви», балете на либретто Назыма Хикмета, балетмейстер собирался убрать устаревшую пантомиму и ввести в классику элементы народного танца. Что необычно для того времени, балет задумывался как совместная постановка в традициях «Русского балета» Дягилева. Музыку для него специально сочинял азербайджанский композитор Ариф Меликов. Декорации заказали Симону Вирсаладзе, который и раньше способствовал тому, чтобы Рудольф стремился менять свой сценический образ.
