Fu fondato nel 1893 e si affiliò alla Football League nel 1920. Escluso dalla Third Division South in favore dell'Ipswich Town alla fine della stagione 1937-1938, tornò nella serie di vertice 12 anni più tardi, dopo l'espansione da 88 a 92 club del campionato. Alla fine degli anni ottanta andò due volte vicino alla promozione in seconda divisione, ma un successivo periodo di declino condusse la società alla quasi retrocessione nella Football Conference nel 1993. Dal 2000 al 2005 ha militato nella seconda serie per la prima e unica volta nella sua storia, raggiungendo il miglior piazzamento nel 2002-2003, con l'undicesimo posto.
La stagione 2012-2013 è la stagione della rinascita per il Gillingham piazzatosi 1º nella Football League Two con ben 91 punti e raggiungendo la prima storica promozione in League One.
Blu, bianco
Inghilterra
.svg){kind=small}
.svg){kind=small}
