The club was established in 1885 as Coleshill & District, playing their first match against Acocks Green in November that year. After being renamed simply Coleshill, the club later became Coleshill Town. They played only friendly and cup matches for the first two decades of their history until joining the Senior Division of the Birmingham Youth & Old Boys League in 1906. They moved to the Sutton & Erdington Division for the 1907–08 season, before returning to the Senior Division in 1909, going on to win both the Coleshill Charity Cup and Tamworth Nursing Cup in 1909–10. In 1912 the club transferred to the Trent Valley League. In their first season in the league they were runners-up, as well as winning the Chapel End Cup. After World War I the club reformed as Coleshill United and joined Division One of the Sutton & District League. They were Division One champions in 1952–53 and 1954–55, before returning to the Birmingham Youth & Old Boys League in 1956, joining the Suburban Division. After winning the division in 1958–59, the club were promoted to the Mercian Division, in which they were runners-up the following season. They were Mercian Division runners-up in 1966–67 and moved up to Division Two of the Worcestershire Combination. The club finished as runners-up in their first season in the division, after which the league was renamed the Midland Combination. Coleshill were Division Two champions in 1969–70, but were not able to take promotion due to their Memorial Ground not meeting the required standards. However, after moving to Pack Meadow in 1974, they were Division Two runners-up in 1974–75 and were promoted to Division One. Although the club finished bottom of the division in 1978–79 and 1980–81, they were reprieved from relegation. The club won the Walsall Senior Cup in 1982–83, and in 1983 Division One was renamed the Premier Division. Coleshill were runners-up in 1983–84. They remained in the Premier Division until being relegated at the end of the 1999–2000 season. The club were promoted back to the Premier Division the following season after finishing fourth in Division One. The 2007–08 seasonsaw Coleshill win the Premier Division title, earning promotion to the Midland Alliance. When the league merged with the Midland Combination to form the Midland League in 2014, the club became members of the Premier Division. They were runners-up in its inaugural season, and again in 2016–17, a season which also saw them reach the semi-finals of the FA Vase, eventually losing 6–1 on aggregate to South Shields. In 2017–18 the club were runners-up in the Premier Division, earning promotion to Division One Central of the Southern League
