Vasco da Gama was established in 1980, carrying the name of famed Portuguese explorer Vasco da Gama. Being mainly a lower league club, Vasco won promotion to the National First Division in 2003, after being crowned champions of the Vodacom Second Division. In their first season of first division football they finished 5th, giving themselves the opportunity to build on their previous league performances.
After a successful 2005/2006 season, Vasco featured in the promotional playoffs, beating Bush Bucks in the semi-final. They lost 1–0 in the playoff finals to a Benoni Premier United team, which included Bafana Bafana players Bernard Parker and Tsepo Masilela. In 2008 they won the Vodacom League and regained promotion into the National First Division once again.
Vasco secured promotion to the PSL when they beat Black Leopards 2–1 (aggregate score 3–2) in a promotional play-off at Parow Park on March 7, 2010.
After only one season in the PSL Vasco was relegated finishing 15th on the log and losing the promotion/relegation playoffs.