Anatole Fistoulari naît au sein d'une famille de musiciens russes : son père, le chef d'orchestre Gregor Fistoulari, avait étudié avec Rimsky-Korsakov et Anton Rubinstein. Instruit par son père, Anatole dirige pour la première fois un orchestre à seulement huit ans[1], où il interprète une œuvre complexe de mémoire[2] : la Sixième symphonie, Pathétique, de Tchaïkovski à l'opéra de Kiev. Puis il dirige à travers la Russie. Sa carrière se développe en dehors de l'Union soviétique ; dès 1920, il voyage en Roumanie et en Allemagne : à treize ans, il dirige notamment à Berlin, Hambourg et Dresde[2]. Puis il s'installe à Paris où en 1933, sa première mission est de diriger pendant plusieurs saisons le Grand Opéra russe de Paris[1], dont le prestige tenait principalement à la basse Fédor Chaliapine au Théâtre du Châtelet. En 1937, il commence à collaborer avec les Ballets russes de Léonide Massine à Monte-Carlo[1], et avec qui il mène une tournée à travers l'Europe et l'Amérique. En 1939, il s'engage dans l'armée française[3], puis après l'armistice, s'enfuit en Angleterre où il s'installe[1]. En 1943, il épouse l'artiste Anna Mahler (une des filles du compositeur) et est nommé directeur musical de l'Orchestre philharmonique de Londres. Il est naturalisé en 1948[1]. Sa carrière est étroitement liée à la Grande-Bretagne et à cet orchestre, avec qui il réalise des tournées hors du Royaume-Uni. Il est invité au MET en 1955 et effectue une tournée en URSS avec le Philharmonique de Londres. Après son divorce, il se remarie avec la violoniste Elizabeth Lockhart en 1956.
