He started coaching in the college ranks in 1962 at Hardin-Simmons University. As a condition of taking the Hardin-Simmons job, Henson insisted that the team (and thus the school) be racially integrated, a condition to which the university agreed. In 1966, he took over at his alma mater, New Mexico State University. In his first season at NMSU, the Aggies rebounded from a 4–22 record in the prior season to finish 15–11 and went to the NCAA Tournament. In 1970, Henson would help lead the Aggies to the Final Four for the only time in the school's history. Henson and future NBA players Jimmy Collins, Sam Lacey, and Charlie Criss lost in the tournament semifinal to eventual champion UCLA, the third time in three years the Aggies lost to UCLA in the tournament. Henson coached at New Mexico State for nine seasons, with six trips to the NCAA Tournament and four twenty-win seasons.