Podczas próby reprezentant Stanów Zjednoczonych, Peter Czerniszew przypadkowo uderzył w nogę Denkowej rozcinając jej mięsień i dwa ścięgna, co nie tylko wykluczyło ją z udziału w mistrzostwach, ale również uniemożliwiło poruszanie się przez kolejne trzy miesiące.
thumb|left|Denkowa i Stawiski (w środku) na podium zawodów NHK Trophy 2004
W 2000 r. zmienili lokalizację treningową z rodzimej Sofii na rosyjskie Odincowo, gdzie do 2005 r. trenowali pod okiem Aleksieja Gorszkowa i choreografa Siergieja Petuchowa. W sezonie 2001/02 wygrali swoje pierwsze zawody z cyklu Grand Prix – Bofrost Cup w Niemczech. W swoim drugim występie na igrzyskach olimpijskich w Salt Lake City byli na siódmym miejscu. W kolejnym sezonie, na mistrzostwach Europy w 2003 w Malmö zdobyli srebrny medal, przegrywając jedynie z Rosjanami Iriną Łobaczową i Ilją Awierbuchem. Podczas mistrzostw świata w 2003 stanęli pierwszy raz na podium mistrzostw świata, zdobywają brązowy medal za Kanadyjczykami Bourne/Kraatz oraz ponownie za duetem Rosjan Łobaczowa/Awierbuch. W sezonie 2003/04 byli niepokonani w zawodach Grand Prix, jednak zarówno na mistrzostwach Europy, jak i mistrzostwach świata zdobywali srebrne medale przegrywając z Rosjanami Tatjaną Nawką i Romanem Kostomarowem.