Fleet Town FC was officially formed in 1890 when the club was simply known as Fleet FC, making it the oldest sports club in the town, although some believe a football team existed in Fleet before then. The centenary was celebrated in 1990 with a Centenary Scroll being presented by The FA to the club, together with a commemorative plaque from Hampshire FA.

In the early days Fleet FC played at the bottom of the Views where Campbells Close is today. Later they moved to Watsons Meadow in Fleet Road, roughly opposite where Travis Perkins now stands. It was during this time that a young, future Prime Minister, Clement Atlee, played for the club, his aunt living in a house that backed onto this original ground.

In 1923 Lord Calthorpe of Elvetham Hall made available the site of the present ground in Crookham Road, and the club moved to its new home in March of that year, playing their first match on 3rd March 1923. The ground was subsequently bequeathed to the District Council with the proviso that it would continue to be for the use of Fleet FC, so Calthorpe Park was born, the same name now used for the large park/recreation ground behind the club.

From 1923 up until World War II Fleet FC ran two Saturday teams and a Wednesday XI in the Aldershot and Basingstoke Leagues. During the war the club competed in the War Emergency League before returning to the Aldershot and Basingstoke Leagues when hostilities ceased. Fleet FC started to play matches in light and dark blue strip in the mid 1920s and this has remained the club colours ever since.

A supporters club was formed in 1953 and this was instrumental in laying a new pitch, building of the pavilion and finally getting floodlights installed.

On the pitch the club entered the Hampshire League in 1961 and in 1963 changed its name to become Fleet Town FC. This move obviously inspired all concerned and the team went on to win Division 3 of the Hampshire League with 50 points from 30 games (2 for a win), scoring more goals than any other team in the three divisions (113). From then on Fleet Town FC gradually moved through the divisions, finally winning promotion to the Athenian League in 1977.

The next few years were a very poor spell in the club's history as it struggled to meet Athenian ground regulations and drifted into other minor leagues. At this time Fleet Town FC could have disappeared without trace until a new chairman arrived and revitalised the club culminating in it being accepted in the Wessex League for the 1989/90 season. After six years of steady progress the club gained promotion to the Southern League (sponsored by Beazer Homes at the time) as Wessex League Champions, in the 1994/95 season. Then followed four seasons in the Southern League where the club struggled at the wrong end of the table although during this time it won the Russell Cotes Cup and the Aldershot Senior Cup. Unfortunately in 1999/00, its fifth season in the Dr Martens Southern League, the club were relegated back to the Wessex League.

The first season back in the Jewson Wessex League, under the management of Wayne Wanklyn, saw a steady performance with the club finishing in a creditable 4th position. After a poor start to season 2001102 Steve Beeks was appointed manager in October 2001. This heralded a change in fortunes for the first team who only lost two games through to the end of the season. Fleet Town FC finished runners up in the League Cup and League Competitions and gained promotion back into the Southern League

The 2002/03 season, the club's first back in the Southern League, saw Beeks resign before the end of September, due to a poor start in the League and elimination from the three major cup competitions. Former Birmingham & Southampton full back Mark Dennis and professional cricketer Adi Aymes took over as joint managers and Fleet Town FC eventually finished 14 points clear of a relegation place, and again won the Russell Cotes Cup.

The 2003/2004 closed season saw another change in management with Mick Catlin taking over, having been reserve team manager at Havant & Waterlooville FC. A disappointing season saw Fleet Town FC finishing bottom of the Eastern Division of the Southern League although by a stroke of good fortune the non-league pyramid restructuring for 2004105 season meant that the club retained their status at Step 4 and played in the Isthmian League.

2004/05 season, the club's first in the Ryman Isthmian League Division 1, saw yet another change in management, with Catlin being replaced by Paul Holden in November. A rollercoaster season ended with the club's Division 1 status only assured on the very last day of the season as Fleet Town FC finished in 19th position. Off the pitch saw an extensive refurbishment of the clubhouse and the links between the senior teams and the colts' and girls' teams becoming stronger than before.

Fleet Town FC started the 2005/06 season with a new management team of ex-England International Andy Sinton assisted by Steve Mellor, inspiring the dub to make dramatic strides both on and off the pitch. 'The Blues' were in the running for a play-off place right up until the end of March when results dipped in the final run. That said, the first team had their highest ever finish in non-league football (14th), crowds were up by 20%, the team went the furthest ever in the FA Cup (a 2-0 defeat to Bishops Stortford in the 2nd Qualifying Round) and the season was concluded with a 2-0 success over Andover to win the Basingstoke Senior Cup for the first time. Add to this the Reserves finishing 4th in their league and the Youth team reaching the Hampshire Youth Cup final against Eastleigh and finishing 3rd in their league.

Season 2006/07 brought a lot of optimism to the club as Andy and Steve moved into their second year as a management team. A stronger squad saw the Blues were top of the table at Christmas before they finally finished in 5th place. In a pulsating play-off semi-final they lost 2-1 to Tooting & Mitcham. The team also reached the final of the Hampshire Cup (losing 2-1 to Aldershot but did gain some cup success to win the Russell Cotes Cup (1-0 v Gosport Borough). So for the second year history was made with not only the highest league placing ever but three cup finals.

For season 2007-08 the FA moved the club to the BGB Southern League, South West Division. It didn't take the Blues long to adjust and they again had a record breaking season. Right up until the last few games they were in with a chance of automatic promotion but eventually had to accept 2nd spot behind Farnborough. This, however, was their highest ever non-league placement and again played in front of record crowds (averaging just under 200). It was heartbreak in the play-offs though as the team again lost in the semi-final, this time an injury time penalty that gave Uxbridge a 2-1 victory. Fleet did however reach four cup finals, winning three: Russell Cotes, Aldershot Senior and Basingstoke Senior Cups. They also went the furthest so far in the FA Cup before losing 2-1 at Havant & Waterlooville in the 3rd Qualifying Round - and of course it was H & W who lost to Liverpool at Anfield later in the competition!