Henderson accepted an athletic scholarship to attend the University of Maryland, where he played for the Maryland Terrapins football team from 1999 to 2002. He holds three NCAA records: career total tackles per game (12.5), season unassisted tackles with 135 in 2002, and career unassisted tackles per game (8.8). He was recognized twice as a first-team ACC selection (2001, 2002), twice as the ACC Defensive Player of the Year (2001, 2002), and twice as a consensus first-team All-American twice (2000, 2001). As a junior in 2001, he was honored as the ACC Player of the Year. As a senior in 2002, he was the recipient of the Chuck Bednarik Award and Butkus Award, recognizing him as the best college defensive player and best college linebacker, respectively, in America. He was also selected as the defensive most valuable player in the Terrapins' 30–3 victory over the Tennessee Volunteers in the 2002 Chick-fil-A Peach Bowl.
On December 15, 2006, Henderson agreed to a five-year contract extension with the Vikings. The deal was reportedly worth over $25 million with $10 million guaranteed.
In Week 13 of the 2009 season, Henderson suffered a broken left femur during a game against the Arizona Cardinals. The injury occurred when his leg twisted violently as he was trying to tackle Tim Hightower and hit Jamarca Sanford's helmet. He was removed from the field on a motorized cart, accompanied by his younger brother and teammate Erin. Henderson stayed overnight in Phoenix for surgery, and missed the rest of the season. He made a full recovery in time for 2010 training camp. After what was described as a "remarkable recovery", Henderson was selected for the 2011 Pro Bowl.