During his lifetime, Henderson received some recognition, apart from an elaborate sendoff from his Second Baptist Church of Falls Church when he left for Alabama in 1965. The Fairfax County Council on Human Relations, where he had served as program chairman, gave him a testimonial in 1960. His Falls Church/Fairfax County NAACP branch also celebrated its 50th anniversary shortly before his departure. In 1972, Black Sports magazine cited Henderson as "one of the foremost black Americans of all time." In 1973, Henderson was elected Honorary President of the North American Society for Sport History. In 1974, along with Joe Louis, Jackie Robinson, Jesse Owens, Bill Russell and Althea Gibson, he became an inaugural member of the Black Athletes Hall of Fame.