Born in Semipalatinsk, Kazakhstan, Gracheva studied at the Kazakh Ballet School in Alma-Ata. In 1986, after winning second prize for the juniors at the International Ballet Competition in Varna, she was admitted to the Moscow College of Choreography where she studied with Sofia Golovkina.
After completing her training, she joined the Bolshoi Ballet in 1988, making her debut as a soloist. Rehearsed under Galina Ulanova and later Marina Kondratieva, she created the leading roles in the classical repertoire and as well as those in many works by contemporary choreographers. She quickly became the Bolshoi's leading dancer, earning the title of prima ballerina after dancing Nikiya in the 1991 production of La Bayadère.
Among the awards she has received are the Prix Benois de la Danse (1992), the Gold Medal at the Japan International Ballet Competition (1995), the People's Artist of Russia award (1996) and the State Prize of the Russian Federation (1997). In 2001, she was awarded the Russian Order of Honour.