Dallas CowboysRediger
Henderson blev valgt i første runde (18. samlet) af NFL-draften i 1975, som en del af Dallas Cowboys Dirty Dozen-draft. Som rookie fokuserede han på special teams. Han returnerede en omvendt aflevering til en 97 yard kickoff-retur til et touchdown (den fjerde i franchisens historie) i den anden kamp mod St. Louis Cardinals. Han blokerede et punt i den fjortende kamp mod New York Jets.
I 1976 konkurrerede han med D.D. Lewis om den startende strongside linebacker-position. Han forblev som backup og central special teams spiller. Han blokerede et punt ud af end zone for en safety i den tolvte kamp mod St. Louis Cardinals.
I 1977 blev han udnævnt til startende strongside linebacker i stedet for Randy White, som blev flyttet til defensive tackle. Han lavede 53 tackles, 3 interceptions, et sack (uofficielt) og 2 fumble recoveries. Han returnerede en interception til en 79-yard touchdown mod Tampa Bay Buccaneers. Han hævdede også, at han introducerede crossbar slam dunk-ceremonien i NFL i slutningen af spillet. Han førte holdet med 7 tacklinger i Super Bowl XII. Henderson gav sig selv øgenavnet “Hollywood” på grund af sit flamboyante spil og sin meget synlige livsstil.
I 1978 kunne han ikke starte i 3 kampe på grund af en ankelskade. Han returnerede en interception til en 68 yard touchdown (herunder en tværgående slam dunk) i 28-0 NFC-mesterskabssejren mod Los Angeles Rams. Før Super Bowl XIII startede han en ordkrig mod Pittsburgh Steelers, som endte med, at han delte en forside af Newsweek-magasinet med quarterback Terry Bradshaw. Han fastgjorde også Bradshaws arme, hvilket gjorde det muligt for linebacker Mike Hegman at stjæle bolden og løbe 37 yards for et touchdown i Super Bowl XIII. Han blev udvalgt til Pro Bowl i slutningen af sæsonen.
Selv om han havde et stort potentiale som spiller, begyndte Hendersons destruktive livsstil med stoffer og alkohol at indhente ham. Under mange kampe sniffede han flydende kokain fra en inhalator, som han gemte i sine bukser. Den sidste dråbe kom i 1979, under den tolvte kamp mod Washington Redskins på RFK Stadium. Mens hans hold blev slået solidt med 34-20 på nationalt fjernsyn, muggede Henderson for kameraet og viste lommetørklæder med Cowboys-holdets logo. Da han blev interviewet om det, gav han holdkammeraten Preston Pearson skylden og sagde, at Pearson havde bedt ham om at vise lommetørklæderne, som Pearson markedsførte, som en tjeneste. Træner Tom Landry blev så vred over episoden, at han efter at have truet med at give ham waive, i stedet deaktiverede Henderson for resten af sæsonen ved at sætte ham på reserve-pensionistlisten. Ifølge kilder tæt på holdet havde Landry ikke til hensigt, at Henderson nogensinde skulle spille for Cowboys igen, selv om træneren stadig var personligt glad for Henderson.
San Francisco 49ersRediger
Den 15. maj 1980 blev han handlet til San Francisco 49ers i bytte for et fjerde runde draftvalg (#91-Scott Pelluer). Den 19. september blev han waived efter kun at have spillet én kamp. Henderson mente, at 49ers-træner Bill Walsh lossede ham, fordi han mistænkte ham for at være afhængig af kokain.
Houston OilersRediger
Den 24. september 1980 skrev han under som free agent med Houston Oilers. Han optrådte kun i seks kampe på grund af en hamstringskade og spillede i Oilers’ playoff-nederlag til Oakland Raiders. Han blev ikke genforhandlet efter sæsonen.
Miami DolphinsRediger
I februar 1981 blev han en af de første fodboldspillere, der offentligt indrømmede, at han havde et stofproblem, og med hjælp fra NFL meldte han sig selv til et rehabiliteringsprogram for stofmisbrugere. Den 10. juni skrev Henderson under med Miami Dolphins, men pådrog sig det, der viste sig at være en nakkeskade, der satte en stopper for karrieren, i den sidste preseason-kamp mod Kansas City Chiefs. Den 31. august blev han sat på den skadede reserveliste. Han blev ikke genforhandlet efter sæsonen.