Seura perustettiin vuonna 1976, kun kaupungin entinen seura Stevenage Athletic meni konkurssiin. Aluksi seuran nimi oli Stevenage Borough. Se liittyi 1980 United Counties Football Leagueen, jossa se voitti ensimmäisellä kaudellaan 1. divisioonan ja nousi liigan päätasolle. Vuonna 1984 Stevenage siirtyi Isthmian Leaguen 2. divisioonaan.
Stevenage nousi neljän kauden aikana vuosina 1990–1994 kolme sarjaporrasta ylöspäin Isthmian Leaguen 2. divisioonasta konferenssiin. Seura voitti konferenssin kaudella 1995–1996, mutta sen nousu 3. divisioonaan evättiin, koska seuran kotikenttä ei täyttänyt vaatimuksia.
Stevenage pelasi konferenssissa kunnes se voitti sarjan kaudella 2009–2010 ja nousi kakkosliigaan, jossa se sijoittui kaudella 2010–2011 kuudenneksi ja nousi pudotuspelien kautta ykkösliigaan. Konferenssivuosinaan Stevenage voitti FA Trophy -cupin 2007 ja 2009 ja eteni FA Cupissa parhaimmillaan neljännelle kierrokselle kaudella 1997–1998. Kauden 2010–2011 FA Cupissa Stevenage pääsi myös neljännelle kierrokselle voittamalla kotonaan valioliigaseuraNewcastlen 3–1. Kaudella 2011–2012 Stevenage eteni ensimmäisen kerran FA Cupin viidennelle kierrokselle, jolla se hävisi uusintaottelun Tottenhamia vastaan 1–3 pelattuaan ensimmäisen ottelun tasan 0–0.
Vuonna 2014, kolmen ykkösliigassa pelatun kauden jälkeen, Stevenage putosi takaisin kakkosliigaan.
