Den gamla klubben grundades redan 1897 och spelade under de tre sista säsongerna fram till 1992 i Football League Fourth Division. På grund av stora ekonomiska problem tvingades man lägga ned verksamheten i samband med att säsongen 1992/93 skulle börja.
Den nya klubben bildades genom att ungdomsklubben Maidstone Invicta FC togs över. Eftersom man saknade en lämplig hemmaarena fick man börja långt ned i ligasystemet, i Kent County League Division Four säsongen 1993/94. Den vann man direkt och flyttades upp till Division Two på grund av att ligan strukturerades om. Även den divisionen vann klubben direkt och gick upp till Division One. Där bytte klubben namn till Maidstone United FC, som den gamla klubben hade hetat, men det dröjde fyra säsonger innan man vann divisionen 1998/99 och gick upp till Premier Division. Under den andra säsongen där, 2000/01, kom man tvåa och ansökte om att få komma med i Kent League, vilket accepterades.
Till den första säsongen i Kent League tvingades man spela sina hemmamatcher i Central Park i Sittingbourne, då arenan i Maidstone inte höll måttet. Samma säsong ställde man upp i FA Vase för första gången. Klubben vann Kent League direkt efter ett avgörande i sista omgången och man vann även ligans cup och därmed "dubbeln". Trots ligasegern blev klubben inte uppflyttad till Southern Football League på grund av oklarheter kring hyresavtalet på Central Park. Oklarheterna medförde även att klubben nästa säsong flyttade sina hemmamatcher till en närbelägen arena kallad Bourne Park. Under den säsongen spelade man för första gången i FA-cupen. I ligan ledde en annan klubbs nedläggning under slutet av säsongen till att man bestämde ligamästaren genom att räkna ut hur många poäng klubbarna tagit per match. Maidstone United och en annan klubb hade fått ihop 63 poäng på 30 matcher, men en tredje klubb hade ett bättre snitt med 62 poäng på 29 matcher. Man kan säga att Maidstone United förlorade ligasegern med 0,14 poäng. Å andra sidan vann klubben Kent Senior Trophy för första gången.
Maidstone United vann Kent League för andra gången säsongen 2005/06 och vann även cupen. Den här gången fick klubben tillstånd att gå upp till Isthmian League Division One South, på nivå 8 i Englands ligasystem för fotboll. Samtidigt fick klubben hyra mark i Maidstone där man kunde bygga en ny hemmaarena och slippa spela i Sittingbourne.[1]
Klubben vann genast Isthmian League Division One South och flyttades upp till Isthmian League Premier Division (nivå 7). Där tillbringade man fyra säsonger, men kom som bäst på 15:e plats. Under den här tiden flyttade man sina hemmamatcher till The Homelands i Ashford, vilket inte blev någon succé. Efter 2010/11 års säsong åkte Maidstone United ned till Division One South igen, vilket var klubbens första nedflyttning.
Sommaren 2012 invigdes klubbens nya hemmaarena Gallagher Stadium med en träningsmatch mot Brighton & Hove Albion inför 2 226 åskådare. Arenan hade kostat 2,6 miljoner pund att bygga. Redan under första säsongen på den nya arenan gick klubben upp till Premier Division efter seger i kvalet. Året efter vann man Isthmian League Cup, och nästföljande säsong, 2014/15, tog man hem Premier Division och gick upp till National League South (nivå 6). Samma år gick man även till andra omgången i FA-cupen efter att i första omgången ha slagit ut Stevenage från League Two.
Under klubbens första säsong i National League South kom man trea och vann sedan kvalet efter en dramatisk final där straffar fick avgöra. Klubben var därmed kvalificerad för National League (nivå 5).
