The club was established in 1973 as Villa Star Football Club. They were renamed Continental Star in 1975 and joined a league for the first time in 1976 when they became members of Division One of the Central Birmingham Alliance. The club were Division One runners-up in their first season, earning promotion to the Premier Division. They went on to win the Premier Division title the following season, as well as the Surry Trophy. The club then joined the Kings Norton League, winning Division One at the first attempt. They subsequently transferred to the Warley Alliance League and won back-to-back league titles in 1979–80 and 1980–81 before moving to Division Four B of the Birmingham Works League.