She graduated from the Bolshoi School in 1899 and joined the Bolshoi Ballet, where she was most admired as a character ballerina. She danced with the Diaghilev Ballet from its beginning in 1909, dancing major roles throughout the entire history of the Diaghilev Ballet. Fedorova continued to dance with the Bolshoi until 1917, dancing also with Diaghilev's and Anna Pavlova's companies. Her husband was Pyotr Olenin, a Russian opera singer and opera director. After his death in 1922 she immediately went into exile in France, where she continued to dance ballet.
Her last performance was with the Diaghilev Ballet in 1928. Then her illness took over. She endured her ordeal courageously, drifting from one mental institution to another. In 1963 at the age of eighty-three her obituary read, "She lived quietly between outbursts of consciousness and delirium.". Among her students is Cuban prima ballerina assoluta/choreographer Alicia Alonso.