Cleopatra was first performed at a benefit in St. Petersburg at the Maryinsky Theatre on March 8, 1908. It was called Nuit d"Egypte at that time. It was originally staged and choreographed by Fokine, solely to Arensky's score. Most of the costumes that were used were borrowed from La Fille du Pharaon and Aida, only soloist costumes were sketched by Leon Bakst. The set came from one of the operas in the Maryinsky's repertoire, but was touched up by Maryinsky stage designer, Oreste Allegri.
On June 2,1909, Diaghilev's Ballets Russes performed it as Cleopatra at the Theatre du Chatelet as part of their first season in Paris. Fokine talked Diaghilev into using a student of his, a non-professional dancer, for the part of Cleopatra, Ida Rubinstein. The sets and costumes were designed by Leon Bakst a the suggestion of Alexandre Benois.
In 1917, while on their Latin American tour, the set for Cleopatra was destroyed in a fire; in July 1918 Diaghilev ordered a new set to be designed by Robert Delauney. He ordered sketches of the costumes for Lubov Tchernicheva and Leonide Massine, from Delauney's wife Sonia.
After attending the opening night of Cleopatra's debut in Berlin, Kaiser Wilhelm II, urged members of his Society of Egyptology to study Bakst's mise-en-scene.