In January 2001, Valeri Bondarenko was appointed as a manager. Bondarenko began the season by winning the Estonian Supercup but failed to defend the Meistriliiga title, finishing the season in third place behind the winners Flora and runner-ups TVMK. In 2002, Pasi Rautiainen took over as a manager. Under Rautiainen, Levadia finished the 2002 Meistriliiga season second, just two points behind Flora. After the season, Rautiainen left the club and returned to Finland for personal reasons and was replaced by Franco Pancheri. Pancheri coached Levadia for just 9 Meistriliiga matches, before he was sacked due being unable to maintain the level achieved with Rautiainen. In June 2003, Levadia hired former Estonia national football team manager Tarmo Rüütli and finished the season in third place.
Under Prins, Levadia won two consecutive Meistriliiga titles in 2008 and 2009 and an Estonian Cup in 2010. In August 2010, Prins was sacked due to disagreements with the club's board and replaced by Levadia II manager Aleksandr Pushtov. Levadia finished the 2010 season second behind Flora. During the 2010–11 winter transfer window, Levadia lost several key players, including Estonian international players Tarmo Neemelo, Eino Puri and Vladimir Voskoboinikov. In July 2011, Pushtov was sacked after disappointing results in the Meistriliiga and the Champions League and replaced by Sergei Hohlov-Simson. Levadia finished the 2011 season in fourth place, lowest since the club was promoted to the Meistriliiga.