However, the club’s ground in Maidstone was nowhere near Kent League standards so the Stones agreed to share Sittingbourne’s Central Park stadium while trying to overcome various legal obstacles in the way of a move to a new ground in the town at James Whatman Way. In its first Kent League season since reformation, Maidstone won the Kent League and Cup double under the management of Jim Ward. However, the club could not gain promotion to the Southern League Eastern Division because of problems with the lease on Central Park. The lease problems were not solved and during the 2002 close season both Sittingbourne and Maidstone moved out of Central Park to a new ground, named Bourne Park, which was built on the same complex using the old training pitch.

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’. 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. In the league, the Stones looked destined to win a second successive title but after a poor run-in, coupled with the withdrawal from the league of Faversham Town, the club bizarrely lost the championship by 0.14 of a point (the League Management Committee decreed that the title would be awarded to the club with the highest earned points per match average, so with Maidstone and Thamesmead Town achieving 63 points from 30 games, the unusual situation arose that the championship was won by Cray Wanderers with 62 points from 29 games). The Stones did pick up some silverware that season, winning both the Kent Senior Trophy and the Kent Charity Cup, but this was overshadowed by continuing lease problems, which meant another attempt to gain promotion to the Southern League was knocked back.

The years 2003 till 2005 contained two indifferent seasons for the Stones, on the pitch at least. 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. However, construction of the stadium could not begin until a lease for the site was agreed with its owners, the Ministry of Defence. The 2005–06 season saw Maidstone, now managed by Lloyd Hume after a spell in charge from Mal Watkins, win the Kent League title. They spent the season toe-to-toe with Beckenham Town before securing the championship on the final day of the season. The title win meant the club finally gained promotion to Step 4 of the non league pyramid, joining the Isthmian League Division One South. However perhaps more importantly, the club’s bid to return to Maidstone was another step closer when a 99-year lease was signed for the land at James Whatman Way, meaning the club was now free to start building on it.