Der Verein wurde im Jahr 1893 als New Brompton Football Club gegründet und änderte 1913 seinen Namen in Gillingham. 1920 fand der Klub erstmals den Weg in die Third Division der Football League, wurde dann aber 1938 als Tabellenletzter der Third Division South nicht wiedergewählt und musste in die Southern League absteigen. Als „Non-League-Club“ hatte man am 10. Januar 1948 im FA Cup gegen die Queens Park Rangers mit 23.002 Zuschauern den bisher größten Besucherzuspruch. Nachdem Gillingham 1950 in die dritte Liga zurückkehren konnte, spielten sie in den darauffolgenden 50 Jahren stets in den untersten zwei Ligen der Football League, wobei ihnen 1964 und 1974 der jeweilige Aufstieg aus der Fourth Division gelang, denen jedoch 1971 und 1989 Abstiege folgten. In den 1980er-Jahren scheiterte der Verein unter den Trainern Gerry Summers und Keith Peacock häufig nur knapp am Aufstieg in die zweite Liga. Zu dieser Zeit entwickelten sich in Gillingham die Karrieren von Spielern wie Micky Adams, Steve Bruce und auch Tony Cascarino, der seinerzeit für einen Satz Trainingsanzüge und Wellblech verpflichtet und nachher für 225.000 Pfund an den FC Millwall verkauft wurde.
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.
