Klub z hrabstwa Kent, który w 2000 roku, po 107 latach istnienia, po raz pierwszy awansował na drugi poziom ligi angielskiej.
Gillingham od początku gra na Priestfield. Pierwszy mecz na tym terenie klub, wtedy jeszcze pod nazwą New Brompton, rozegrał 2 września 1893 roku z rezerwami Woolwich Arsenal. Do 1947 roku obiekt oficjalnie nazywał się Priestfield Road. Rekord frekwencji, 23 002 widzów, padł 10 stycznia 1948 roku na meczu Pucharu Anglii z Queens Park Rangers.
Stadion przez dziesięciolecia prawie się nie zmieniał. Przebudowę rozpoczął dopiero po 1995 roku prezes Paul Scally: w 1997 roku stanęła trybuna Gordon Road, w sezonie 1999/2000 nowe trybuny Rainham End i główna Medway Stand, a po sezonie 2003/2004 w miejscu Town End zbudowano odkrytą trybunę imienia Briana Moore'a, byłego dyrektora klubu i komentatora telewizji ITV.
Klub założono w maju 1893 roku w pubie Napier Arms jako New Brompton FC. Rok później przeszedł na zawodowstwo i był wśród założycieli Southern League; w 1895 roku wygrał jej drugą ligę i awansował po meczu barażowym ze Swindon Town, wygranym 5:1. Obecną nazwę Gillingham przyjął przed pierwszą wojną światową, a w 1920 roku znalazł się wśród założycieli Third Division w Football League.
W kolejnych 20 latach najwyżej zajął siódme miejsce w Third Division South. W 1938 roku piąty wniosek o ponowny wybór do ligi przepadł i miejsce Gillingham zajęło Ipswich Town. Zarząd zdecydował się kontynuować działalność głosem rozstrzygającym prezesa. Po wojnie drużyna wygrywała rozgrywki Kent League i Southern League, a w 1950 roku, gdy powiększano trzecie ligi z 22 do 24 zespołów, wróciła do Football League z największą liczbą głosów.
Pierwszy tytuł ligowy przyszedł w 1964 roku. Drużyna Freddiego Coxa, słynąca z defensywy i niepokonana w tamtym sezonie ligowym u siebie, wygrała Fourth Division dzięki lepszemu stosunkowi bramek od Carlisle United, z którym miała tyle samo punktów. Tytuł zapewniła sobie 30 kwietnia 1964 roku zwycięstwem 1:0 w Newport po golu George'a Francisa.
W 1987 roku, w pierwszej edycji baraży, Gillingham wyeliminował Sunderland dzięki bramkom zdobytym na wyjeździe; pięć z sześciu goli w dwumeczu strzelił Tony Cascarino. Finał ze Swindon Town wymagał powtórki, którą klub przegrał 0:2 na Selhurst Park. Kilka lat później drużyna była bliska spadku z Football League i utrzymała się dopiero dzięki wygranej 2:0 z Halifax Town w ostatnim meczu u siebie w 1993 roku. W 1995 roku klub trafił pod zarząd komisaryczny, a kontrolę nad nim przejął Paul Scally.
Pod wodzą Tony'ego Pulisa Gillingham awansował w 1996 roku. W 1999 roku po raz pierwszy zagrał na Wembley, w finale baraży Division Two z Manchesterem City. Prowadził 2:0 po golach Carla Asaby i Roberta Taylora, ale rywale wyrównali w 90. minucie i w doliczonym czasie, a potem wygrali rzuty karne 3:1. Rok później drużyna Petera Taylora wróciła na Wembley i w finale z Wigan Athletic przegrywała w dogrywce 1:2. W ostatnich minutach gole Steve'a Butlera i Andy'ego Thomsona dały jej zwycięstwo 3:2 i pierwszy w historii awans do Division One. W tym samym sezonie klub doszedł do ćwierćfinału Pucharu Anglii, w którym przegrał z Chelsea 0:5.
Na drugim poziomie Gillingham grał do 2005 roku; spadł w ostatniej kolejce gorszym bilansem bramek o jednego gola. W 2009 roku wygrał na Wembley finał baraży League Two z Shrewsbury Town 1:0 po golu głową Simeona Jacksona w 90. minucie. Mistrzostwo League Two zdobyła w 2013 roku drużyna Martina Allena; tytuł zapewnił remis 2:2 z AFC Wimbledon 20 kwietnia 2013 roku.
W 2022 roku klub spadł z League One w ostatniej kolejce. W grudniu 2022 roku większość udziałów kupił amerykański przedsiębiorca Brad Galinson, a Scally, właściciel od 1995 roku, zachował pakiet mniejszościowy.
