Walton Casuals FC was formed in July 1948, owing its early origins to members of the Armed Forces.
The earliest roots of the club lead back to World War II. Following the conclusion of the war, a group of ex-servicemen returned to their council homes in the Walton-on-Thames area. They soon decided to form an "illegal" Sunday football team, who would go on to play friendlies against other "illegal" teams throughout the 1946-47 and 1947-48 seasons. They adopted the name White City FC, due to the outside walls of their houses being painted that colour.
In 1948, they decided to become a legitimate Saturday club, and Walton Casuals as they are currently known were founded. They became affiliated with the Surrey FA and acquired the use of a pitch at Elm Grove Recreation Ground. The club started off in Division One of the Surrey Intermediate (Central) League and gained promotion to the Premier Division in 1952–53. Walton Casuals would go on to finish as runners-up on 3 occasions: 1954–55, 1956–57 and 1964–65. The Surrey Intermediate (Central) League disbanded in 1965 and the club moved into the League’s Western Section for three seasons.
In 1969, the Casuals joined the new Surrey Senior League and moved into its most notorious home at Franklyn Road Sports Field, later known as the Waterside Stadium. Two years later the club became founder members of the Suburban League, playing one season at Walton & Hersham’s Stompond Lane ground before moving to Addlestone's Liberty Lane ground for eight seasons. The club then returned to Franklyn Road, where the Reserves had continued playing in the Surrey Combination League. The 1982–83 season saw the Casuals win their first major honour, becoming champions of the Suburban League Southern Section and setting a league record of going 23 games unbeaten under manager Kim Harris. The following year the Stags were runners-up behind Sutton United, and in the 1986–87 season reached the Surrey Premier Cup Final, only to lose to Croydon.
Subsequent years saw the club slip into a steady decline, regularly finishing in the bottom two of the Suburban League. After 21 years of competing in the Suburban League, the club decided to switch to the Surrey Premier League in June 1992 in order to join the pyramid system. A year of consolidation paved the way for major changes at Franklyn Road the following summer, as Kim Harris was reappointed as manager after a successful spell at Hersham RBL and the club expanded into both Sunday and youth football. In 1993–94, the Casuals won the Surrey Premier League Challenge Cup, defeating Holmesdale after a replay, and in 1994–95 the club finished runners-up to Chobham in the league. They were also were losing finalists to Vandyke in the Challenge Cup.
During the summer the club was promoted to the Combined Counties Football League, and the first four seasons of senior football proved a real struggle. Finishing bottom of the league in 1996–97, the club avoided relegation thanks to the Combined Counties League exercising its prerogative to maintain a minimum number of clubs in the Premier Division. With the help of Walton charities, the installation of floodlights at Franklyn Road was completed in February 1999, a major hurdle overcome as far as ground requirements were concerned. The appointment of Mick Sullivan and Garry Clark as joint managers in the summer of 1999 brought about a dramatic improvement in results. As well as a best-ever finish of 5th in the league, the club won the League Cup in 2000, beating Viking Greenford 4–2 in the final. The following season was also a relatively successful one, with a placing of 7th in the table and another appearance in the League Cup final, beaten 3-0 by double-winners Cove.
Although 2002–03 proved a disappointment as the club finished in a lowly 18th spot, the seeds of success had been sown with Spencer Collins taking over as first-team manager in November 2002. As a team capable of much better things slowly began to take shape, ex-West Ham United player Tony Gale was installed as Director of Football. After more team-building in 2003–04, and a big jump up the table to finish in 7th spot, the club took the Combined Counties Football League by storm the year after, finishing 26 points clear at the top of the table. Initially failing an FA ground inspection, the club launched a successful appeal and achieved their dream of promotion to the Isthmian League Division One for 2005–06.
The club finished 15th in their maiden season in the Isthmian League, while regularly finishing in the bottom half in subsequent seasons. In 2009–10 the club achieved its best run in the FA Cup reaching the Third Qualifying Round, before losing to Staines Town. The club appointed Neil Shipperley manager in the summer of 2010 and managed to finish in 12th place, their best finish in the league at the time.
During early 2011 the club opened a new clubhouse and new changing facilities, with Mick Sullivan returning to the helm in October, following the resignation of Shipperley. After being sacked a year later, Danny Carroll took over as manager. With a reprieve saving the Stags in the 2012–13 season, the club appointed ex-Kingstonian assistant manager Mark Hams as manager, along with his brother Neil as assistant. The duo rejuvenated the squad and guided Walton to their highest ever league finish of 9th. However, after nine defeats in as many league games, Mark and Neil Hams left their positions at the club by mutual consent in September 2014.
Tony Gale and Anthony Gale were drafted in as caretaker managers, and immediately picked up the club's first win of the season, securing a 1–0 victory in a trip to Redhill. In November 2014, defender Liam Collins was appointed first team manager with teammate Simon Huckle named assistant manager. Collins was able to secure the club's safety with a comfortable 18th-placed finish. At the end of the season, Che announced his intentions to step down from his management position to focus on his last few seasons on the field, while Huckle parted ways with the club to join Redhill.
Anthony Gale was announced as first team manager shortly before the start of the 2015-16 season and guided the club to 18th in his first full season in charge. The following season saw the Casuals equal their best ever FA Cup run, reaching the Third Qualifying Round before defeat to Westfields.
The club moved into the Elmbridge Xcel Sports Hub, a £20 million sports complex built on the site of the Waterside Stadium, for the 2017–18 season and enjoyed great success in their opening year. Losing just two home games throughout the campaign, Walton secured qualification for the play-offs in the final 15 minutes of the season with a dramatic conclusion at Ashford United. A semi-final tie at Cray Wanderers ended in a 5–2 victory for the Casuals and booked a final with previous runners-up Corinthian-Casuals. After a goalless 120 minutes at King George's Field, a penalty shoot-out was required to determine the winner. Max Hustwick, Harry Mills, Josh Kelly and Lartey Sarpong all converted from the spot while Denzel Gerrar made the winning save to earn a place in the seventh tier for the first time in the club's history.