Continental Star won Division Four B at the first attempt. They went on to win Division Three B, Division Two and Division One B in successive seasons, before finishing as runners-up in Division One A in 1985–86. In 1989–90 the club were Division One champions, also winning the WBA Shield and the Sports Argus Shield. After winning won the league's Premier Division, Aston Villa Shield and WBA Shield in 1992–93, they moved up to Division Three of the Midland Combination. Their first season in Division Three saw them finish as runners-up, earning promotion to Division Two. The club were Division Two champions in 1995–96 and were promoted to Division One. They went on to finish as Division One runners-up the following season, securing promotion to the Premier Division.