1999 beschlossen der Erstligist Tallinna Sadam und der alte FC Levadia Maardu, der vormals als Olümpia Maardu angetreten war und 1998 nach der Übernahme durch den UkrainerViktor Levada umbenannt worden war, zu fusionieren. Während die neu gegründete Mannschaft unter dem Namen FC Levadia Maardu in der Meistriliiga antrat, spielte die zweite Mannschaft als FC Maardu in der zweiten Liga.
Bereits im ersten Jahr gelang Levadia der erste Meistertitel, der 2000 verteidigt werden konnte. Als 2001 die zweite Mannschaft den Aufstieg schaffte, erhielt diese den Namen Levadia Tallinn, während die erste Mannschaft weiterhin als Levadia Maardu antrat. 2002 stellte Viktor Levada sogar drei Mannschaften in der Meistriliiga, als der FC Levadia Pärnu für eine Saison erstklassig spielte.
2002 gelang dem Verein der erste Pokalsieg der Vereinsgeschichte. Pikanterweise standen sich Levadia Tallinn und Levadia Maardu im Finale gegenüber, das Spiel endete 2:0 für Tallinn. Im Supercupfinale im selben Jahr musste man sich allerdings Flora Tallinn im Elfmeterschießen geschlagen geben.
Vor der Saison 2004 nannte sich Levadia Maardu in Levadia Tallinn um. Gleichzeitig gab der ursprüngliche FC Levadia Tallinn seine Lizenz zurück, die an JK Merkuur Tartu vergeben wurde. Am Ende der Saison stand der dritte Meistertitel des Vereins zu Buche. Es gelang sogar das Double, nachdem der FC TVMK Tallinn im Pokalfinale deutlich mit 3:0 besiegt wurde. Den Supercup konnte man jedoch erneut nicht gewinnen, Flora Tallinn war erneut stärker und siegte mit 2:1.
Im folgenden Jahr stand man erneut im Finale des Pokals und durch ein spätes Tor von Vitali Leitan gelang dem Vizemeister ein 1:0-Erfolg. Allerdings war TVMK Tallinn im Finale des Supercups stärker und man konnte diesen Titel erneut nicht gewinnen.
2006 gelang der vierte Meistertitel der Vereinsgeschichte. 30 Siege und 114 geschossene Tore bedeuteten am Ende 11 Punkte Vorsprung auf Vizemeister JK Trans Narva. Im selben Jahr schaffte der Klub als erster estnischer Verein die Qualifikation für die erste Runde des UEFA-Pokals, als Twente Enschede mit 1:1 in den Niederlanden und einem 1:0-Heimsieg bezwungen werden konnte. Dort erwies sich Newcastle United jedoch als zu stark und konnte beide Partien für sich entscheiden.
Das Hinspiel endete mit 1:0 für União Leiria. Das Spiel wurde aber mit 0:3 gegen Leiria gewertet, da União Leiria einen nicht spielberechtigten Spieler eingesetzt hatte.
