Występy miały być kontynuowane w Londynie i 16 czerwca 1961 grupa udała się na lotnisku Le Bourget. Tam radzieccy agenci nie zezwolili Nuriejewowi na lot do Londynu, lecz nakazali mu powrót do ZSRR samolotem do Moskwy, który odlatywał niewiele później. Dzięki pomocy dwójki francuskich przyjaciół udało mu się poprosić na lotnisku o azyl polityczny. Po tym głośnym, a dla niego przełomowym kroku artysta otrzymał angaż w International Ballet, którego dyrektorem był Marquis du Cuevas.

Duże znaczenie w karierze Nuriejewa odegrała Margot Fonteyn, z którą stworzył liczne duety. Ich występy zachwycały publiczność tym razem spoza obszaru Związku Radzieckiego. Niezapomniane kreacje tworzył też wraz z innymi wielkimi primabalerinami: Sylvie Guillem, Lynn Seymour, Evą Evdokimovą, Carlą Fracci, Marcią Haydee czy Natalią Markarowa i Karen Kain. Głośną kreacją był duet męski o silnej wymowie homoerotycznej z Christopherem Gable w 1964 w Images of Love MacMillana. Od tego momentu jego kariera nabrała tempa, występował w takich przedstawieniach jak Bajadera i Raymonda dla Royal Ballet. Współpracował również z baletem Fredericka Ashtona – Marguerite and Armand. W 1964 można było go podziwiać w Wiedniu w partiach z Jeziora Łabędziego. Artysta pracował też dla Baletu Królewskiego w Szwecji.