« A la fin du Lac, quand elle a quitté la scène dans son grand tutu blanc
je l’aurais suivi jusqu’au bout du monde. » Rudolf Noureev
En 1961, Noureev fut invité au Gala annuel organisé par Margot Fonteyn à Londres pour la Royal Academy of Dancing. Il voulut danser le Spectre de la Rose avec elle, mais Margot le dansait déjà avec John Gilpin, et de toute façon elle se demandait comment elle pourrait être à son avantage aux côtés de ce « jeune russe ». C’est pourquoi Noureev dansa le Cygne Noir avec Hightower et un solo, Poème Tragique, que Frederick Ashton régla pour lui.
Après ce gala, le Royal Ballet l’invita à danser Giselle avec Margot Fonteyn la saison suivante, ainsi que le Lac des Cygnes, le pas de deux de Don Quichotte, les Sylphides et la Belle au Bois Dormant avec les artistes invitées, Sonia Arova et Yvette Chauviré. Dans l’intervalle, Noureev dansa également avec Erik Bruhn, Arova et Hightower à Cannes et Paris, dans des extraits créés ou montés par les deux hommes. Il fit ses débuts à la télévision new- yorkaise (remplaçant Bruhn blessé dans le pas de deux de Festival des Fleurs à Genzano avec Tallchief), puis sur scène avec le Ballet de l’Opéra de Chicago de Ruth Page.
Les bases de toute sa carrière étaient ainsi jetées : un lien durable avec le Royal Ballet, de fréquentes apparitions avec d’autres troupes, ses débuts de producteur et de chorégraphe, et surtout son association avec Fonteyn. Tous deux dansaient avec de nombreux autres partenaires qui s’amélioraient ainsi par voie de conséquence, mais ils tiraient leur plus grande fierté de ce qu’ils réussissaient ensemble. A 23 ans, Noureev donna à Fonteyn, alors âgée de 42 ans, un élan d’énergie nouveau et une autre compréhension de son art ; elle l’inspira et l’aida à se fixer.
Ils apprirent beaucoup l’un de l’autre et c’est ensemble qu’ils dansaient le mieux. Il voulait danser avec elle à Léningrad pour montrer le résultat de leur travail (malheureusement, lorsqu’il fut enfin autorisé à retourner danser à Léningrad, Fonteyn ne dansait plus et lui-même était sur le déclin).
Rudolf Noureev expliquait ainsi leur succès phénoménal : » Ce n’est pas elle, ce n’est pas moi, c’est le but que nous poursuivons ensemble « . Ils demeurèrent amis toute leur vie durant.