Bristol City und FC Portsmouth

Im Jahr 2005 wechselte der 17-jährige Stephen Henderson aus seiner irischen Heimat in die Jugendakademie des englischen Erstligisten Aston Villa. Im Sommer 2007 unterschrieb er einen Einjahresvertrag bei Bristol City, nachdem sein Vertrag in Birmingham ausgelaufen war. Am 11. August 2007 debütierte er für den Zweitliga-Aufsteiger bei einem 2:2 gegen den Ligakonkurrenten Queens Park Rangers in der Football League Championship 2007/08. In den anschließenden Spielzeiten wurde er an unterklassige Vereine ausgeliehen um Spielpraxis zu sammeln. Die Saison 2010/11 spielte er auf Leihbasis für den Drittligisten Yeovil Town und bestritt dabei 33 Ligaspiele.

Am 8. Juli 2011 unterzeichnete Henderson einen Dreijahresvertrag beim FC Portsmouth. In die Football League Championship 2011/12 startete er als Ersatz für Stammtorhüter Jamie Ashdown, konnte diesen jedoch im Saisonverlauf verdrängen. Da der FC Portsmouth sich in erheblichen finanziellen Schwierigkeiten befand, wechselte er am 16. März 2012 auf Leihbasis zu West Ham United. Mit seiner neuen Mannschaft erreichte er aufgrund eines 2:1-Erfolges im Play-off-Finale gegen den FC Blackpool den Aufstieg in die Premier League, blieb jedoch selbst bis zum Saisonende ohne einen Einsatz als Ersatz für Stammkeeper und Nationaltorhüter Robert Green.

West Ham United und Charlton Athletic

Im Mai 2012 verpflichtete ihn West Ham auf fester Vertragsbasis und stattete ihn mit einem bis 2015 gültigen Vertrag aus. Da er in der Premier League 2012/13 auch nach dem Vereinswechsel von Robert Green Ersatz hinter dem neuverpflichteten Jussi Jääskeläinen blieb, wurde er bereits im Oktober an den Zweitligisten Ipswich Town ausgeliehen. Für sein neues Team bestritt er 24 Spiele in der Football League Championship 2012/13.

Im Oktober 2013 folgte ein weiteres Leihgeschäft zum AFC Bournemouth. Bereits in seinem zweiten Einsatz für Bournemouth zog er sich in der Partie bei Nottingham Forest eine Schulterverletzung zu, die für das vorzeitige Ende der Ausleihe sorgte und ihn bis zum Saisonende außer Gefecht setzte.

Am 21. Juli 2014 wechselte Stephen Henderson zum Zweitligisten Charlton Athletic. Bei seinem neuen Verein startete er als Stammtorhüter in die Football League Championship 2014/15, ehe ihm eine erneute Schulterverletzung im November 2014 eine abermalige dreimonatige Zwangspause bescherte. Insgesamt bestritt er 31 Ligaspiele bis zum Saisonende für den Tabellenzwölften. In der anschließenden Spielzeit stieg Henderson mit seiner Mannschaft als Drittletzter in die drittklassige EFL League One ab.

Nottingham Forest

Nach dem Abstieg mit Charlton Athletic unterschrieb er im Sommer 2016 einen Dreijahresvertrag beim Zweitligisten Nottingham Forest. Ende Januar 2018 verlieh in Forest bis zum Saisonende der EFL League One 2017/18 an den Drittligisten FC Portsmouth. Anfang Dezember 2018 wurde er per Notfallleihe zunächst für eine Woche an den Drittligisten Wycombe Wanderers abgegeben, bei dem die beiden Torhüter Ryan Allsop und Yves Ma-Kalambay verletzt ausgefallen waren. Nach einem eindrucksvollen Auftritt bei seinem Debüt, einem 1:0-Sieg gegen den FC Barnsley, wurde die Leihe um eine weitere Woche verlängert. Bei Nottingham war er zeitweise hinter Costel Pantilimon, Jordan Smith und Luke Steele nur noch vierter Torhüter.

Crystal Palace

Nach seiner Freistellung in Nottingham im Anschluss an die Saison 2018/19 schloss sich Henderson im Juli 2019 dem Erstligisten Crystal Palace an. Dort unterzeichnete er einen Vertrag für die Spielzeit 2019/20. In den folgenden zwei Jahr als „Backup“ kam er in keinem Pflichtspiel der A-Mannschaft zum Einsatz und er kehrte im September 2021 zu seinem Ex-Klub Charlton für einen Einjahresvertrag zurück.