After his sophomore year, Henderson transferred to Lehigh Senior High School. Due to transfer rules, he was not able to play during his junior year. He used that time to change his physique and, in his senior year, earned a scholarship to Florida State University.
Henderson was selected by the Raiders in the 3rd round of the 2007 draft. In his second year, he started several games at left tackle in place of injured veteran Kwame Harris, and was the Raiders' full-time left tackle in 2009 and 2010. Oakland did not re-sign him for the 2011 season.