Il Sutton United F.C. venne fondato il 5 marzo 1898 dalla fusione del Guild Rovers F.C. e del Sutton Association F.C; gioca nel Borough Sports Ground, impianto inaugurato nel 1912.
Il Sutton Utd ha militato in diversi campionati calcistici; inizialmente nell'Athenian League (lega dei dintorni di Londra, vincendola tre volte), successivamente si è trasferito nell'Isthmian League (sud-est dell'Inghilterra), riuscendo a vincerla in cinque occasioni. Nel corso degli anni '60 il club raggiunge inoltre per due volte la finale di FA Amateur Cup, perdendola in entrambe le occasioni (si tratta più precisamente delle stagioni 1962-1963 e 1968-1969). Un altro successo rilevante è la Coppa Anglo-Italiana 1979 (vinta sconfiggendo in finale il Chieti); l'anno seguente ha invece perso contro la Triestina nella finale della medesima competizione. Nella stagione 1980-1981 raggiunge invece la finale di FA Trophy, coppa nella quale è invece semifinalista nelle stagioni 1992-1993 e 1999-2000.
Nella stagione 1988-1989 nel terzo turno di FA Cup sconfigge il Coventry City: si tratta di uno dei rari casi in cui un club non-League sconfigge un club di prima divisione; tra i protagonisti della partita ci sono anche diversi giocatori che in seguito hanno giocato a livello professionistico (tra i quali Paul Rogers e Paul McKinnon). Nel 2004 è stato invece uno dei club che hanno fondato la Conference South (campionato di 6ª serie inglese).
Nella stagione 2016-2017 accedono al quarto turno di FA Cup (sedicesimi di finale) battendo il Leeds Utd (club di seconda divisione) per 1-0. Negli ottavi di finale è sorteggiata contro l'Arsenal rimediando una sconfitta casalinga per 2-0.
Nella stagione 2020-2021 il Sutton vince la National League, approdando per la prima volta nella sua storia nella Football League.
