Stefanova was born in Sofia, Bulgaria. When she was four years old, she received chess lessons from her father, Andon Stefanov, a designing artist.
In 1989, Stefanova won the Under-10 girls section at the World Youth Chess Championships in Aguadilla, Puerto Rico. In 1992, she played, at the age of 13, in her first Chess Olympiad in Manila, Philippines. In the same year she became European Under-14 girls’ champion at the European Youth Chess Championship in Rimavská Sobota. Stefanova won the Bulgarian women’s championship in 1995.
She finished equal fourth in the 4th Hawaii International Chess Tournament in 1997 scoring 7 points out of 10 games. Thanks to this result Stefanova achieved her first Grandmaster norm. In January 1998, her FIDE rating broke into the top ten of women worldwide. She played for the Bulgarian open team at the 2000 Chess Olympiad. In 2001, Stefanova finished equal first (second on countback) in the 19th Andorra Open.
In June 2002, she won the 3rd European Individual Women’s Chess Championship in Varna. Stefanova was awarded the title of Grandmaster at the FIDE Presidential Board meeting in Doha in July 2002. At the end of July 2002, she won the Wismilak International Chess Tournament, a category 8 (average 2446) round-robin tournament in Surabaya, Indonesia, scoring 9.5/11 with a performance rating of 2750.
She participated in the 2004 Corus B tournament in Wijk aan Zee, the Netherlands: she scored 6/13 with a rating performance of 2537, placing ninth out of fourteen participants.
Stefanova became the tenth Women’s World Chess Champion in June 2004 by winning a 64-player knockout tournament held in Elista, Kalmykia, under the auspices of FIDE.
She won the women’s individual rapid tournament of the 2008 World Mind Sports Games in Beijing. In 2012, Stefanova won the Women’s World Rapid Chess Championship. She was the runner-up in the Women’s World Chess Championship 2012, losing to Anna Ushenina in the final on the tie-break.