Henderson, futbol kariyerine doğduğu şehrin takımındaSunderland altyapısında başladı. A takımla ilk maçına ise 1 Kasım 2008'deChelsea deplasmanında 5-0 yenildikleri maçla çıktı.[4]
Ocak 2009'da bir alt ligin ekiplerindenCoventry takımına kiralandı. Burada sezon sonuna kadar oynama şansı yakalayan Henderson profesyonel kariyerinin ilk golünü de Coventry formasıylaNorwich City takımına attı.[5]
2009-2010 sezonuyla birlikte yenidenSunderland'e dönen Henderson, gösterdiği başarılı performansla takımındaYılın En İyi Genç Oyuncusu ödülünü aldı.[6]
2011 yılındaFIFA tarafından gelecek vadeden en iyi 13futbolcu arasında gösterilen Henderson, takımında da üst üste ikinci kezYılın En İyi Genç Oyuncusu ödülüne layık görüldü.[7]
8 Haziran 2011'deLiverpool veSunderland futbolcununLiverpool'a transferi konusunda anlaştıklarını açıkladılar.[8] Resmî ağızlardan oyuncunun bonservis bedeli konusunda bir açıklama yapılmamış olsa daLiverpool'un sözleşme fesih bedeli olarakSunderland'e yaklaşık 20 milyon £ ödediği bilinmektedir.
Henderson'a yeni kulübünde daha önceXabi Alonso veMilan Jovanovic tarafından giyilen 14 numaralı forma verildi. İngiliz orta saha oyuncusu yeni takımıyla ilk maçına ise 13 Ağustos 2011'dePremier League'in ilk haftasında eski takımı Sunderland karşısında çıktı.[9]