The club in the meantime obtained an official legal status by its registration with the Corporate Affairs Commission of Victoria in 1977. The late 1970s and early 1980s the Club went through what many regard as its "Golden Era". In 1980, the Club won the "Top 4" play-off series beating Sydney City by 4 goals to nil in Canberra. Towards the end of the 1980s, the Club encountered difficulties both on and off the park. It was twice relegated (1987 and 1989) but managed to be promoted the next year back into the NSL. During this period for Heidelberg players such Juan Toro, Derek Lea and Charlie Yankos participated in this golden era. In the 1990s it continued to play a prominent role in Australian soccer, operating with a yearly budget of more than $500,000. However, in 1995 the Club suffered a major setback when it was excluded from the National Soccer League along with Melbourne Zebras and the Parramatta Eagles. Soccer Australia, led by David Hill began the "cleansing process" of the league trying to remove all remnants of ethnicity by forcing Clubs to change their names. Alexander The Great made an attempt to rejoin the National League in a joint partnership arrangement with the Collingwood Football Club and whilst things looked promising at the start, pressure from the AFL saw the venture collapse by the end of its inaugural season. The team did however manage to win the National League Cup in 1996 emulating the feats of Heidelberg United who won the cup for the first time three years earlier in 1993. Victorian Premier League (1996–2013) On their return to the Victorian league in 1996, Heidelberg had a reasonably successful season, eventually losing in the Grand Final against Altona Magic in penalties after scores were locked at 3–3 after extra time. In 1998 they found themselves relegated, but won promotion back at their first attempt, rejoining the VPL in 2000, and winning the title in 2001. Their rollercoaster recent history however saw them relegated the next season, until they found themselves back in the VPL once more in 2005, and finishing runners up to Green Gully. A solid season in 2006 saw them reach the Preliminary Final, where they were knocked out by Altona Magic in extra time. An inconsistent season in 2007 saw the Bergers finish 8th and miss out on finals. Celebrating the 50-year anniversary of