Fistoulari was born into a musical family in Kyiv, Russian Empire, now Ukraine.^[1] His principal teacher was his father, the conductor Gregor Fistoulari, who had studied with Nikolai Rimsky-Korsakov and Anton Rubinstein.^[1] Anatole conducted for the first time, at the age of seven, Pyotr Ilyich Tchaikovsky's 6th Symphony, the Pathetique,^[3][4] at a charity concert at the Opera House in Kyiv.^[5] He then conducted a concert of the Imperial Court Orchestra in Odessa from memory.^[5] At the age of 13 he went to Bucharest, where he was invited to conduct Samson and Delilah at the Opera House.^[2] Next he went to Germany and in Berlin undertook engagements with the State Opera Orchestra and the Blüthner Orchestra, as well concerts in Hamburg and Dresden, and received advice from Arthur Nikisch.^[5]

In 1933, Fistoulari was chosen to conduct several seasons of the Grand Opera Russe at the Théâtre du Châtelet in Paris with the Russian bass Feodor Chaliapin, having already conducted over one hundred performances by a small Russian company which had toured France, Belgium, Spain and Italy.^[5] He also led The Barber of Seville at the Théâtre des Champs-Élysées with a cast from La Scala including Stabile, Lomanto, Chaliapin and Vichnevska.^[5] In 1933, he began his collaboration with Léonide Massine's Ballets Russes in Paris, touring in London and to 61 cities in the United States in 1937. Fistoulari also gave orchestral concerts during this time.^[5]

In 1939 Fistoulari joined the French army, but was invalided out and after the Fall of France managed to get to Cherbourg, having left all his possessions in Paris, and escaped to England where he remained for the rest of World War II. In 1943, he was appointed principal conductor of the London Philharmonic Orchestra; a post he held through 1944.^[1] During this period, he had a contract for 120 concerts, a great responsibility for the youthful conductor. His repertoire widened to include items like his father-in-law Gustav Mahler's Fourth Symphony in his busy concert schedule. After he was let go by the London Philharmonic he tried to organize his own orchestra called The London International, a pick-up group which gave concerts in London and around the UK and Ireland but which only lasted a year.^[6] In 1948, he became a British citizen. He conducted opera and concert schedules especially with either the London Philharmonic or London Symphony Orchestras. He conducted operas in New York and was a guest conductor in many countries. In 1956, he toured France and the USSR with the London Philharmonic Orchestra.

Operatic work in Britain began with a The Fair at Sorochyntsi production that toured the country,^[2] starting at the Savoy Theatre in 1941 and notching up 200 performances around the UK. He introduced Dmitri Shostakovich's Symphony No.6 to the UK in 1943.^[5] He was a guest conductor with the Royal Ballet, London in 1954 and 1955.^[1] Outside the UK, he conducted orchestras in Israel and New Zealand among other countries.^[1] During the 1950–51 season at the Teatro Liceo, Barcelona he led a series of performances of three Russian works, Khovanshchina, Le Coq d'Or, and The Invisible City of Kitezh.^[7] In 1956 he toured Russia as conductor with the London Philharmonic with stops in Leningrad and Moscow.^[1]

Fistoulari made a number of studio recordings from the late 1940s through the mid-1960s, most of them dance or ballet music, overtures and concertos. Fistoulari specialised in the interpretation of ballet music. He was also a noted conductor of Tchaikovsky and the Russian School, as well as romantic and impressionistic French music. In the 1950s his recordings were mostly for MGM, Decca, EMI, RCA and Mercury. Of special note are the Mercury performances of Sylvia by Léo Delibes and Giselle by Adolphe Adam. He recorded all three Tchaikovsky ballets, recording Swan Lake for Decca three times—once, in 1952, (slightly abridged) with the London Symphony—a second performance (of highlights), in stereo with the Concertgebouw Orchestra of Amsterdam in February 1961; and (uncut) in 1973, a Decca Phase 4 three disc set, featuring Ruggiero Ricci as violin soloist. Fistoulari made his last recordings with Decca Phase 4 in the early 1970s, including Tchaikovsky's 4th Symphony. His last recording was in June 1978 with Takayoshi Wanami and the Philharmonia Orchestra in the Mendelssohn Violin Concerto in E minor, Op.64.^{[citation needed]}

Besides his ballet recordings, Fistoulari conducted many well-known singers on record including Jan Peerce, Inge Borkh, Victoria de los Ángeles, and Boris Christoff, pianists like Edwin Fischer, Vladimir Ashkenazy, Clifford Curzon, Wilhelm Kempff, Earl Wild and Shura Cherkassky, as well as violinists such as Yehudi Menuhin and Nathan Milstein.^{[citation needed]}

In 1942 Fistoulari married Anna Mahler, daughter of the composer Gustav Mahler.^[1] She was living in Hampstead, having fled Nazi-occupied Austria.^[2] It was her fourth marriage. They had a daughter, Marina, born August 1943. They separated after the war and Anna moved to California. Their marriage was dissolved around 1956.^[1]

Fistoulari suffered from crippling arthritis during the latter years of his life; and was cared for by his second wife, the Scottish violinist Elizabeth Lockhart.^[4] He died in London at Queen Mary's Hospital on 21 August 1995.^[3]