After a disappointing season in the top-flight, with the first team finishing bottom of the table, the club was relegated. The 2007–08 season however proved to be a huge success with Stars dominating the First Division and securing promotion to the Premier League once again.
They also managed to win the inaugural Baymed Cup in December 2006 beating FC AK in the final.
In the South African PSL, only five non-South African nationals can be registered. Foreign players who have acquired permanent residency can be registered as locals. Namibians born before 1990 can be registered as South Africans.