Celtic haalde Henderson op twaalfjarige leeftijd weg bij Heart of Midlothian. Hij maakte de voorbereiding op het seizoen 2013/14 mee met het eerste elftal, maar werd nadien teruggezet bij het tweede elftal om nog verder te rijpen. Daarnaast speelde hij wedstrijden in de UEFA Youth League. Op 6 december 2013 debuteerde hij voor Celtic in de Scottish Premier League, tegen Motherwell.