A nivel universitario jugó para North Texas Mean Green por tres temporadas, jugó en Sun Bowl de 1958 y su número 28 fue retirado de la universidad.[3] Sería seleccionado en el Draft de la NFL de 1960 en la posición 55 de la quinta ronda por los Pittsburgh Steelers, pero decidió jugar en la American Football League con los Dallas Texans por la cercanía con su ciudad natal.
Haynes ayudó a popularizar la AFL en 1960, siendo elegido como el primer ganador de Player of the Year en la liga, y también ganó el premio a novato del año. fue el primer líder corredor de la AFL con 875 yardas, además de liderar a los Texans en recepciones, regresos de patada, y regresos de patadas de salida. Haynes estuvo tres años en Dallas y dos con Kansas City Chiefs en 1963. Los Chiefs también retiraron el número 28 en reconocimiento a sus logros en la cancha.[4][5] Con su tamaño Haynes era muy efectivo en campo abierto, y regularmente estaba entre los primeros 10 lugares de la AFL entre los corredores (tercero de todos los tiempos),y puso el récord de la AFL con 5 touchdowns en un partido, 19 en 1961, y 46 de por vida. Haynes conserva 10 récords de los Texans incluyendo el de más puntos en un partido (30), más touchdowns en un partido (5), más yardas combinadas (8,442). Era el arma más versátil del entrenador Salón de la Fama Hank Stram de 1960 a 1962, con 43 touchdowns y 4,472 yardas en ese periodo. En 1962 ayudó a los Texans a ganar el campeonato de la AFL en doble tiempo extra a los Houston Oilers. En el partido Haynes anotó dos touchdowns.
Haynes el 30 de septiembre de 1962 ante los Buffalo Bills en el Cotton Bowl tuvo 164 yardas en 16 acarreos con dos touchdowns terrestres, uno de 71 yardas y otro de 13 yardas en la victoria 41–21.[6]
Haynes fue cambiado a l os Denver Broncos antes de la temporada de 1965. Haynes vio el cambio como una retribución por participar junto a otros jugadores de color que boicotearon el Juego de las Estrellas de la AFC de 1965 que originalmente se iba a jugar en New Orleans, pero sería cambiado a Houston luego de las protestas.[7][8] En ese año anotó tres touchdowns terrestres, dos touchdowns por recepción, y un regreso de patada para touchdown. Lideró la liga en regresos de patada (34), regresos de salida (901), yardas por regreso de patada (26.5), y cuarto en la liga en yardas totales (1,404). El 17 de octubre regresó 3 patadas para 140 yardas, imponiendo un récord de franquicia de 46.7 en promedio. En 1966 tuvo 304 yardas terrestres y 480 aéreas, lideró la liga con 11 fumbles. En 1967 jugó para los Miami Dolphins,[9] y los New York Jets.[10]
En sus ocho temporadas como profesional Haynes corrió con el balón 1,036 veces para 4,630 yardas, un promedio de 4.5; recibió 287 pases para 3,535 yardas, promedio de 12.3, y 20 touchdowns; regresó 85 despejes para 875 yardas, promedio de 10.3 y 1 touchdown; y tuvo 121 patadas de salida para 3,025 yardas, un promedio de 25.0 y 1 touchdown. Sus 12,065 yardas combinadas son un récord en la American Football League. Haynes tuvo tres partidos con al menos 100 yardas en 14 o menos acarreos, y fue seleccionado al Segundo equipo histórico de la AFL.
En 2019 la Professional Football Researchers Association nombró a Haynes al PFRA Hall of Very Good Class de 2019.[11]
