Zovu ga najznačajnijim i najpoznatijim plesačem dvadesetog stoljeća, zovu ga legendom baleta. Bio je prvi u svakom smislu: prvi sovjetski izvođač koji se odbio vratiti s međunarodne turneje; prvi koji je postao velika zvijezda na Zapadu; prvi koji je javno priznao da je homoseksualac; i prvi koji je govorio o AIDS-u, od kojeg je umro u 55. godini života.

Godine 1961. njegov Marijinski teatar odlazi na turneju u Pariz. Ignorirajući KGB-ove smjernice o tome kako bi se izvođači trebali ponašati u inozemstvu, Nurejev se mnogo družio s francuskim plesačima, uživao u francuskoj prijestolnici i kasno dolazio u hotel. Sovjetsko kazalište je trebalo otputovati u London, no Nurejev je dobio kartu za Moskvu. Rečeno mu je da ga pozivaju na važnu izvedbu. Osjećajući da će mu zabraniti da putuje u inozemstvo, izabrao je slobodu.

Francuske vlasti su mu dopustile da ostane, a Nurejev počinje dobivati i pozivnice iz raznih kazališta širom svijeta: nastupao je u Londonu, Parizu, Cannesu, Chicagu i New Yorku. U Kopenhagenu je Nurejev upoznao Erika Bruhna koji ga je očarao svojim plesnim vještinama. Dvojica muškaraca su se zaljubila jedan u drugoga te su do Bruhnove smrti 1986. godine bili u otvorenoj i bliskoj vezi.

Nurejev je 1983. godine došao na čelo Baleta pariške Opere. Ubrzo nakon imenovanja, Nurejev je saznao da je HIV pozitivan. Probao je razne terapije, no njegova se snaga smanjivala iz dana u dan. Praktički više nije bio u stanju plesati, a posljednjih je godina života svoju energiju u opadanju posvetio dirigiranju.

Nurejev je umro 1993. godine, te je u skladu s njegovim posljednjim željama, pokopan na ruskom groblju u Sainte-Geneviève-des-Boisu.