The club was formed as a Sunday league team in 1964. They joined Division Two of the Mid-Cheshire League in 1982 and went on to win the division at the first attempt, losing only one game all season and scoring 102 goals in 30 games. The league was then reduced to a single division and the club went on to win the League Cup in 1984–85 and the league title in 1985–86. With the club in financial difficulties, they then merged with Parkway Clayton. After winning the Sentinel Shield and finishing as runners-up in the Mid-Cheshire League in 1986–87, the club were promoted to Division Two of the North West Counties League. Newcastle Town were Division Two runners-up in 1991–92, earning promotion to Division One. The following season saw them win the league's Floodlit Cup. They won the Walsall Senior Cup in 1993–94 and retained it the following season, as well as winning the Sentinel Cup. the club were Division One runners-up as well as winning the Floodlit Cup for a second time in 1995–96. In 1996–97 they reached the first round of the FA Cupfor the first time, losing 2–0 at home to Notts County in front of a record crowd of 3,948 in a match played at Stoke City'sVictoria Ground. The season also saw them finish as runners-up in Division One and win the League Cup. The club went on to finish as runners-up in Division One again in 1999–2000, also reaching the FA Vase semi-finals, where they lost 3–1 on aggregate to Deal Town. In 2004–05 Newcastle Town were Division One runners-up for a fourth time. Division One was renamed the Premier Division in 2008 and the club were Premier Division champions in 2009–10, earning promotion to Division One South of the Northern Premier League; they also won the Staffordshire Senior Cup, beating Port Vale 6–1 in the final. The club were Division One South runners-up the following season, qualifying for the promotion play-offs, but lost 3–0 to Grantham Town in the semi-finals. A third-place finish in 2014–15 was followed by a 3–1 defeat by Sutton Coldfield Town in the play-off semi-finals.
Ground
The club play at the Lyme Valley Stadium on Buckmaster Avenue. The ground doubles as a velodrome, with a cycling track around the pitch. The ground includes a seated stand on one side of the pitch and a covered standing terrace on the other. Both ends of the ground consist of uncovered standing areas. It currently has a capacity of 4,000, of which 300 is seated and 1,000 covered. The ground was also previously used by Stoke City Reserves.
