Barnes attended racially segregated schools. In 1956 he graduated from Hillside High School with 26 athletic scholarship offers. Segregation prevented him from attending nearby Duke University or the University of North Carolina. His mother promised him a car if he lived at home so he attended the all-Black North Carolina College at Durham (formerly North Carolina College for Negroes, now North Carolina Central University). At North Carolina College he majored in art on a full athletic scholarship. His track coach was Dr. Leroy T. Walker. Barnes played the football positions of tackle and center at NCC.