Jüngste Entwicklungen

Im Jahr 1995 befand sich der Verein als Tabellenvorletzter der untersten Profiklasse am Rande des Bankrotts und wurde von Paul Scally, einem Geschäftsmann aus der Büromaterialbranche, für die symbolische Summe von einem Pfund gekauft. Mit ihm wurde Tony Pulis neuer Trainer in Gillingham, der unmittelbar ein Dutzend neuer Spieler verpflichtete. Mit ihnen gelang der sofortige Aufstieg in die dritte Liga. Nur drei Spielzeiten später verpasste der Verein dann einen erneuten Aufstieg in die zweite Liga durch eine Niederlage in den Play-offs gegen Manchester City nur knapp. Nach Toren von Robert Taylor und Carl Asaba lag Gillingham nur zwei Minuten vor Spielende mit 2:0 vorne. Es folgten jedoch noch zwei Treffer von Manchester City vor Ablauf der 90 Minuten zum 2:2. Das anschließende Elfmeterschießen gewann Manchester mit 4:2 Toren.

Zur neuen Spielzeit wurde Pulis entlassen und von Peter Taylor beerbt. Es folgte eine Saison, in der Gillingham nach Siegen gegen die Premier-League-Vereine Bradford City und Sheffield Wednesday erstmals das Viertelfinale im FA Cup erreichen konnte, dort jedoch dem FC Chelsea mit 0:5 unterlag. In der Meisterschaft belegte der Klub den dritten Platz und verspielte durch die Niederlage am letzten Spieltag gegen den AFC Wrexham den direkten Aufstieg und musste wieder in die Ausscheidungsspiele. Nach einem Sieg im Halbfinale gegen Stoke City begegnete man Wigan Athletic im Wembley-Stadion. Nach Ablauf von 90 Minuten trennte man sich mit 1:1 Toren, wobei Iffy Onuora für die Gills getroffen hatte. Obwohl der Verein in der ersten Hälfte der Verlängerung das 1:2 hinnehmen musste, gewann Gillingham nach Toren von Steve Butler und Andy Thomson noch mit 3:2 und stieg erstmals in die First Division (heute Football League Championship) auf.

Da Taylor lediglich einen Ein-Jahres-Vertrag unterzeichnet hatte, konnte er im Anschluss problemlos zum Premier-League-Verein Leicester City wechseln. Daraufhin wurde der ehemalige Mannschaftskapitän Andy Hessenthaler, der schon zuvor Betreuungsaufgaben übernommen hatte, zum Spielertrainer der Mannschaft. Unter seiner Regentschaft schloss er die Spielzeiten bis 2003 mit einem dreizehnten, zwölften und dann elften Platz ab. Zum Abschluss der Saison 2003/04 konnte der Verein dann am letzten Spieltag nach einem 0:0 gegen den FC Walsall mit nur einem Tor Abstand die Klasse halten. Mit John Gorman, der bereits Kotrainer von Glenn Hoddle in der englischen Nationalmannschaft gewesen war, wurde Hessenthaler ein Assistent zur Seite gestellt, nachdem die Saison 2004/05 für Gillingham wenig erfolgreich gestartet war. Als sich die Leistungen der Mannschaften nicht verbesserten, trat Hessenthaler im November als Trainer zurück, spielte jedoch weiterhin in der Mannschaft. Gorman trainierte vorübergehend das Team eigenverantwortlich, bevor er dann zu den Wycombe Wanderers wechselte. Gillingham verpflichtete daraufhin mit Stan Ternent den ehemaligen Trainer des FC Burnley. Trotz einer deutlichen Steigerung stieg der Verein am letzten Spieltag in die Football League One ab, wobei nun Gillingham nur ein Treffer fehlte, weshalb man hinter Crewe Alexandra blieb.