FC Pärnu Levadia was established in 2000. The team was formed out of young local players from Tervis Pärnu and was sponsored by Viktor Levada, who was looking to restructure Levadia's farm club system. 2000 and 2001 saw Pärnu Levadia winning two successive promotions, first to Esiliiga and then to Estonian top-flight Mesitriliiga, where the team was strengthened by some players from the Levadia system, who were not getting enough playing time at either Levadia Maardu (now Levadia Tallinn) or Levadia Tallinn (now Levadia's reserve team). Pärnu Levadia finished bottom of the Meistriliiga in their first and only season in the top-flight. Following the unsuccessful 2002 season, Viktor Levada decided to withdraw his sponsorship from Pärnu and Pärnu Levadia's Esiliiga slot was taken over by Vaprus Pärnu. Pärnu Levadia players who had no contract affiliation with Levadia also joined Vaprus for the following Esiliiga season.
The club was re-established in 1999 as FC Vaprus Pärnu and competed in III Liiga. Vaprus Pärnu won the Western Conference in 2000 and earned promotion to II Liiga. Following the 2002 Estonian football season, Vaprus took over FC Pärnu Levadia'sEsiliiga slot. The originally re-established Vaprus continued as the club's reserve team, while the first team was predominantly formed out of former Pärnu Levadia players. The same season Vaprus suffered relegation from the Esiliiga after the club's license was revoked by the Estonian FA halfway through the season. Vaprus Pärnu won 2005 Esiliiga and was promoted to 2006 Meistriliiga. The team finished 7th in their first season in the top-flight Estonian league. Vaprus finished 2008 Meistriliiga 10th, but managed to avoid direct relegation due to disbandment of TVMK Tallinn. However the team still lost the relegation play-off against Paide Linnameeskond and was relegated.