Klubben ble stiftet i 1893 og ble valgt inn i The Football League i 1920. Det ble utstemt av ligaen til fordel for Ipswich Towm ved slutten av 1937-38-sesongen men returnerte 12 år senere når ligaen ble utvidet fra 88 til 92 klubber.
«The Gills», som er kallenavnet til Gillingham, spiller hjemmekampene sine på Priestfield Stadium i Gillingham.
