Following the sale of Bloemfontein Celtic the previous year, this left the Free State without any representatives in professional football.

[3] Founded in 1977 in a small village of Makwane in an area then known as QwaQwa, the club gained promotion to the National Professional Soccer League in 1986.

The following year, Mike Mokoena revived the club as he bought and renamed the franchise of National First Division side Maholosiane.

The 2006–07 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 won the inaugural Baymed Cup in December 2006 beating FC AK in the final.