Юрий Григорович, 34-летний хореограф, чью первую постановку, «Каменный цветок», сочли революционным отходом от шаблонных драмбалетов, очень распространенных в советских театрах, приступил к очередной масштабной постановке и увидел в восточной пластике и романтической внешности Рудольфа именно те качества, которые требовались для его героя. Григорович был репетитором Рудольфа в «Жизели» и с тех пор стал его поклонником и защитником, находя, что его новаторская манера исполнения близка по духу к тому, что он внедрял в хореографии. В «Легенде о любви», балете на либретто Назыма Хикмета, балетмейстер собирался убрать устаревшую пантомиму и ввести в классику элементы народного танца. Что необычно для того времени, балет задумывался как совместная постановка в традициях «Русского балета» Дягилева. Музыку для него специально сочинял азербайджанский композитор Ариф Меликов. Декорации заказали Симону Вирсаладзе, который и раньше способствовал тому, чтобы Рудольф стремился менять свой сценический образ.

Рудольф внес много своих идей в образ главного героя Ферхада, помогая Григоровичу переосмыслить типичного советского героя-мачо. Больше всего танцовщика вдохновлял «Аполлон Мусагет» Баланчина, его необычайно прозрачный шедевр на музыку Стравинского, который три года назад привозила в Россию труппа Алисии Алонсо. Рудольф тогда без спросу сорвался из Ленинграда, чтобы посмотреть балет в Москве, за что по возвращении его ждал официальный выговор и вычет из зарплаты. Но он ни о чем не жалел. «Я был взбудоражен… я думал: как странно, как необычно, как чудесно!» Передавая свое волнение Григоровичу, Рудольф пытался воспроизвести специфические па, которые он запомнил из балета. «Все вернулось ко мне… и в общем я сказал – ладно, он делал так, и так, и эдак». А поскольку Григорович тоже внедрял новаторские приемы, навеянные персидскими миниатюрами, процесс работы над балетом стал для них взаимовыгодным сотрудничеством. «Они буквально летали, не в силах скрыть взаимное удовольствие», – сказал танцовщик Никита Долгушин.

Начиная с первого появления героя, когда Ферхад вылетал на сцену, Григорович «подгонял» героя под самого Рудольфа. Ферхад не просто оттеняет и поддерживает свою возлюбленную, как партнер в старом балете. Утверждая новый статус мужчины-танцовщика, он в лирическом па-де-де подражает легким газельим прыжкам юной героини и имитирует трепещущие движения ее рук, словно ее зеркальное отражение. Как-то Вирсаладзе сидел в классе и наблюдал за тем, как Рудольф и его партнерша репетируют этот дуэт. Он повернулся к Григоровичу и сказал: «Не думаю, что мы когда-нибудь снова увидим нечто подобное». Но, поскольку финальный прогон «Легенды о любви» проходил на сцене, Рудольф вскоре собрался уходить; репетиция затянулась, а ему еще нужно было поработать с Аллой Шелест над «Лауренсией». «Рудик, ты куда? Я еще не сказал, что мы закончили». – «Юрий Николаевич, я ухожу репетировать нормальные танцы!» – ответил Рудольф и вышел. Григорович пришел в ярость и крикнул ему вслед: если он сейчас уйдет, обратной дороги не будет. Рудольф пропустил его слова мимо ушей. Вера Красовская, которая сидела в зрительном зале, стала свидетельницей этой сцены. Когда стало ясно, что Григорович намерен выполнить свою угрозу, умоляла вмешаться Вирсаладзе, его наставника и близкого друга. По словам Красовской, Вирсаладзе пробовал заступиться за Рудольфа, но у него ничего не вышло. Через два дня Григорович написал на Рудольфа официальную жалобу директору Театра имени Кирова Георгию Коркину:

Однако Рудольф не слишком высоко ценил Григоровича, по чти своего ровесника, который к тому времени успел поставить всего один балет. Кроме того, работа над балетом укрепила в нем желание самому стать хореографом, и позже он обсуждал с Никитой Долгушиным возможность создать произведение на музыку Баха. «Мы знали, что Баланчин поставил Concerto barocco на эту музыку. И хотя мы никогда его не видели, нас вдохновляла одна мысль о том, на что это может быть похоже: мы представляли, что это будет уникально, изящно и грациозно». Для Рудольфа всемогущим, верховным творцом был Баланчин. Тем не менее через месяц, когда «Легенда о любви» была завершена и Рудольф впервые увидел ее на сцене с Александром Грибовым в роли Ферхада, он пожалел о своем поведении, считая, что эта роль стала самой большой упущенной возможностью в его карьере.

Западным критикам трудно понять притягательность «Легенды о любви» (которую Арлин Крос назвала обыкновенным советским китчем), но в России балет считали триумфом, «диссертацией по искусству хореографии». Надеясь, что Сергеев поможет найти выход из тупика, Рудольф пошел к нему просить за себя. Он знал, что Сергеев завидует Григоровичу и может обрадоваться возможности продемонстрировать свою власть. Конечно, Сергеев не только обещал Рудольфу, что в следующем сезоне он будет танцевать Ферхада, но, радуясь возможности заработать доброе имя за то, что помогает танцовщику, обещал ему два важных дебюта: в «Спящей красавице» и «Лебедином озере». «Счет 2:0. Мы победили!» – торжествующе объявил Рудольф Тамаре, как только узнал новость.

В то время они стали почти неразлучными: Рудольф так доверял Тамаре, что делился с ней самым сокровенным – не чувствами, но мыслями о ролях и интригах в театре, зная, что может положиться на ее преданность. Тамара, чье существование было «всецело поглощено Рудольфом», поняла, что влюбилась. Она с нетерпением ждала их долгих совместных прогулок, которые часто продолжались по пять-шесть часов, а в белые ночи – иногда и до утра. Они гуляли по любимому маршруту вдоль Фонтанки на Невский, оттуда на Марсово поле и вдоль Невы, мимо Медного всадника на Исаакиевскую площадь и обратно по Невскому на улицу Зодчего Росси. Однажды Рудольф признался, что после репетиции он допоздна гулял с одним другом. «Где? С кем?» – с подозрением спросила Тамара. «Я гулял с Тейей», – ответил он, описав маршрут, который Тамара считала только «их».

Только той весной Рудольф познакомил Тамару со своим молодым немецким другом (при Любе и Леониде он ни разу не упоминал его имени). Инстинктивно угадав в нем соперника на привязанность Рудольфа, Тамара невзлюбила Тейю с самого начала. Это чувство было взаимным: говоря о Тамаре, Тейя часто называл ее «черной кошкой». Верный своей натуре, Рудольф использовал обоих в своих целях. Он любил фотографироваться, и во время прогулок с Тамарой часто просил ее сфотографировать его. Они выбирали красивые места: на снимках он опирается на перила набережной Фонтанки, стоит перед зданием Театра имени Кирова, Русским музеем, Летним садом… С первой встречи с Тейей, когда он попросил студента снять на камеру выступление «Американского театра балета», он все время смотрел в комнате Тейи многочисленные отснятые им любительские фильмы. «Тема с вариациями» Баланчина, поставленная в честь Петипа, взволновала его так же, как первое знакомство с танцем Эрика Бруна. Хотя Тамара видела всего лишь «прыжки крошечного человечка» в отрывках из «Лебединого озера» и «Дон Кихота», Рудольфа поражал изящный и гибкий почерк Бруна. «На 8-миллиметровой пленке я видел, на что способны его ноги. Мне хотелось этому научиться, понять, как он это делает».