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 Tallinn and runner-ups TVMK Tallinn. In 2002, Pasi Rautiainen took over as a manager. Under Rautiainen, Levadia Maardu finished the 2002 Meistriliiga season second, just two points behind Flora Tallinn. After the season, Rautiainen left the club and returned to Finland for personal reasons and was replaced by Franco Pancheri. Pancheri coached Levadia Maardu for just 9 Meistriliiga matches, before he was sacked due being unable to maintain the level achieved with Rautiainen. In June 2003, Levadia Maardu hired former Estonia national football team manager Tarmo Rüütli and finished the season in third place.
In 2004, Levadia Maardu moved to Tallinn and subsequently became Levadia Tallinn, while previously Tallinn-based reserve team with the same name changed its name to Levadia II Tallinn. Under Rüütli, Levadia Tallinn won the 2004 Meistriliiga season but failed to defend the title in 2005, coming second behind TVMK Tallinn. Levadia Tallinn defeated both Haka and Twente 2–1 on aggregate in the 2006–07 UEFA Cup qualifying rounds but lost to Newcastle United 1–3 on aggregate in the first round. Levadia Tallinn won two more Meistriliiga titles in 2006 and 2007. In 2008, Rüütli left Levadia Tallinn, having been hired by the Estonian Football Association to coach the Estonia national football team and was replaced by the previous assistant manager Igor Prins.
Under Prins, Levadia Tallinn 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 Tallinn manager Aleksandr Pushtov. Levadia Tallinn finished the 2010 season second behind Flora Tallinn. During the 2010–11 winter transfer window, Levadia Tallinn 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 Tallinn finished the 2011 season in fourth place, lowest since the club was promoted to the Meistriliiga.