At Morgan State, Gaines was given his nickname of "Big House": a fellow student saw the 6 ft. 3in., 265 lb Gaines and declared: "You're as big as a house." Gaines played as a lineman for the Bears football team, was a member of the basketball team, and participated in track. Gaines was an All-CIAA selection as a lineman in football all four seasons and twice elected an All-American. When it came to basketball, he said he was "a very average basketball player." In 2004, he explained, "I was an All-America in football, but I was just on the basketball team to have something to do."