Rudolf Nurejew wurde am 17. März 1938 in der Nähe von Irkutsk geboren. Seine Mutter befand sich gerade auf einer Reise mit der Transsibirischen Eisenbahn nach Wladiwostok, wo sein Vater als Soldat stationiert war. Seine Eltern waren Tartaren. Rudolf Nurejew wuchs in einem Dorf bei Ufa in Baschkirien auf und galt schon im Jugendalter als schwieriger Flegel.

Mit siebzehn fuhr Rudolf Nurejew nach Leningrad (St. Petersburg), wo er nach einer dreijährigen Ausbildung bei Alexander Puschkin an der Ballettschule Waganowa Mitglied der Kirow-Truppe wurde. 1958 gewann er den Ersten Preis im nationalen Ballettwettbewerb in Moskau. Innerhalb kurzer Zeit entwickelte sich Rudolf Nurejew zu einem der berühmtesten Ballett-Tänzer Russlands. Als der Kirow-Solotänzer Konstantin Michailowitsch Sergejew (1910 – 1992) aufgrund einer Verletzung ab 1961 nicht mehr auftreten konnte, wurde Rudolf Nurejew sein Nachfolger.

Von einer Gastspielreise nach Paris kehrte Rudolf Nurejew nicht mehr nach Russland zurück, sondern setzte sich am 17. Juni 1961 am Flughafen Le Bourget von seiner Truppe ab und blieb als erster russischer Ballett-Tänzer im Westen. Dafür verurteilte ihn ein sowjetisches Gericht in Abwesenheit zu sieben Jahren Zwangsarbeit. (Erst als das Urteil aufgehoben worden war, konnte er 1989 erstmals wieder in seine Heimat reisen, u. a. zu einem Gastspiel in Ufa.)

Die berühmte Ballett-Tänzerin Margot Fonteyn de Arias (eigentlich: Peggy Hookham, 1919 – 1991) holte Rudolf Nurejew zur „Royal Academy of Dancing“ nach London und sorgte dafür, dass er einen Vertrag für das königliche Ballett erhielt. Rudolf Nurejew und Margot Fonteyn galten auf der Bühne als Traumpaar.

1962 trat Rudolf Nurejew erstmals im Kino auf, in einer Filmversion von „Les Sylphides“. Weitere Filmaufnahmen folgten, darunter auch „Romeo und Julia“ mit Margot Fonteyn (1965). 1972 führte Rudolf Nurejew in Australien erstmals selbst Regie, und zwar in einer Inszenierung des Balletts „Don Quijote“. Von 1964 bis 1988 war er als Tänzer und Choreograf beim Staatsopernballett in Wien tätig, und 1982 erhielt er die österreichische Staatsbürgerschaft. Von 1983 bis 1989 war Rudolf Nurejew Direktor des Opernballetts in Paris. Auf der dortigen Bühne war Sylvie Guillem eine seiner Partnerinnen. 1988 wurde er Ehrenmitglied der Wiener Staatsoper und in die französische „Légion d’honneur“ aufgenommen. Außerdem erhielt Rudolf Nurejew 1992 den „Chevalier de l’Ordre des Arts et Lettres“, den höchsten französischen Kulturorden.

Rudolf Nurejew setzte neue Maßstäbe, und man verehrte ihn als „Tanzgott“. Er gilt als einer der besten Ballett-Tänzer des 20. Jahrhunderts. Man bewunderte nicht nur seine Bühnenpräsenz, sondern auch seine Schönheit und erotische Ausstrahlung.

Zur Förderung von Nachwuchstänzern gründete er die „Rudolf Nurejew Dance Foundation“, der er noch kurz vor seinem Tod 7 Millionen Dollar zukommen ließ.

Zu dem Entschluss, sich in den Westen abzusetzen, mag beigetragen haben, dass Rudolf Nurejew geglaubt hatte, seine Homosexualität in Paris – anders als in seiner Heimat – nicht groß verheimlichen zu müssen und besser ausleben zu können. Zahlreiche homosexuelle Affären werden ihm nachgesagt. Bei einer Tournee begegnete Rudolf Nurejew in Dänemark dem zehn Jahre älteren Ballett-Tänzer Erik Bruhn, der sein langjähriger Geliebter wurde.

Zu Beginn der Neunzigerjahre, als Rudolf Nurejew den Höhepunkt seiner Karriere längst hinter sich gelassen hatte, war nicht mehr zu übersehen, wie krank er war. Vermutlich litt er bereits seit Anfang der Achtzigerjahre an Aids. Am 6. Januar 1993 starb der Vierundfünfzigjährige in Paris.

Mit seinem Roman „Der Tänzer“ setzte Colum McCann dem russischen Tänzer ein literarisches Denkmal.