Initially, Jim Thompson ran the club, but was banned from football for his part in the demise of Maidstone and Dartford, and Paul Bowden-Brown took over as Chairman – a position he retained until 2010.

However, the club could not gain promotion to the Southern League Eastern Division because of problems with the lease on Central Park.

The 2002–03 season saw Maidstone enter the FA Cup for the first time since reformation, and the club was featured on BBC Sport's 'Road to Cardiff'.

[6] The club reached the 2nd qualifying round of the cup, with the highlight of the run coming in the form of a 3–2 win against old foes Tonbridge Angels, with Steve Butler bagging a hat-trick against the Southern League East outfit.

Both campaigns saw the club finish 4th in the league, although this disappointment was offset somewhat by reaching the third qualifying round of the FA Cup in successive years.

Off the pitch, the club took a huge step forward when in November 2004 it successfully applied for planning permission to build a new stadium at James Whatman Way.

The 2005–06 season saw Maidstone, now managed by Lloyd Hume after a spell in charge from Mal Watkins, win the Kent League title.

However the overwhelming success on the pitch was overshadowed by little visible progress being made in the building of the stadium at James Whatman Way.

Before the 2007–08 season had even begun Alan Walker was involved in a freak accident at a coaching course in Belfast which left him temporarily paralysed.

[11] Maidstone struggled in the new surroundings of the Isthmian League Premier Division and spent the majority of the season near the foot of the table, despite having the services of Chris Smalling at their disposal, however they avoided relegation after beating Folkestone Invicta 1–0 on the last day of the season, a result that relegated Invicta in Maidstone's place.

In October 2010 the club was taken over by shareholder Oliver Ash and Terry Casey[17] with Paul Bowden-Brown stepping down as chairman.

[20] Club captain Jay Saunders was appointed caretaker manager until the end of the season,[21] and although he oversaw the team to 5 wins from nine games he could not save Maidstone from relegation.

The club opened the £2.6 million stadium with a showpiece friendly against Brighton & Hove Albion in front of a sell-out crowd.

Maidstone played a goalless draw away to Stevenage of League Two and in the replay at home in front of a capacity crowd went through to the second round proper, winning 2–1.

[29] Maidstone United went on to win the Isthmian Premier title[30][31] following a season-long battle with Margate, then Dulwich Hamlet and finally Hendon.

In the 2015–16 season the team again qualified for the first round proper of the FA Cup where they narrowly lost 1–0 at home to League Two side Yeovil Town in front of a record-breaking crowd of 2,811.

[39] Having defeated Football League sides including Barrow and Stevenage, the Stones subsequently won 2–1 away to Ipswich Town in the fourth round.

In January 2015, there was a "confrontation" between Tonbridge Angels coach Barry Moore and a Maidstone supporter after a game between the sides.

A fanzine site “Plastic Passion” was launched in February 2014, in part to celebrate one of the most successful eras in the club's history.

A second book, this time available in physical form, "Exodus" was published in December 2016, detailing the period between 1988 and 2012 and the struggle to find a permanent home.

The Football League era saw the birth of four fanzines, "Show Me The Way To Go Home", "Spirit of London Road (aka S.O.L.D)", "Yellow Fever", later renamed "Golden Days", and "The Foundation Stone" which ran for just a couple of issues.

By the time the club returned to the Kent League in 2001 the team behind Show Me The Way To Go Home decided to revive it after almost ten years.

It was named after the line uttered by commentator Derek Rae when Frannie Collin scored the winner for Maidstone against Stevenage in an FA Cup first round replay in 2014.

Note: Flags indicate national team as defined under FIFA eligibility rules; some limited exceptions apply.

The club also runs an academy, giving over fifty 16 to 18-year-old players the chance to study, train and play at the Gallagher Stadium.

Players study for a BTEC Level 3 in Sport and a range of vocational football-related qualifications, and also play in the Conference Youth Alliance.

[45] The club's record attendance came at the Gallagher Stadium, when a capacity 4,175 spectators saw Maidstone play Hampton and Richmond on 4 May 2022 in the final game of the 2021–22 season to see the Stones lift the National League South trophy, the previous highest attendance was 4,105 on 15 July 2017 in a pre-season match to celebrate the fifth anniversary of the Gallagher Stadium.