Bates accepted a football scholarship from the University of Arizona. He was moved between running back and wide receiver, but was mainly used as a kickoff returner, averaging 23.7 yards on 45 kickoff returns during his college career.
As a true freshman in 1989, he had 14 returns for a 24.1-yard average. As a sophomore in 1990, he ranked among the All-purpose leaders in the Pac-10 and received honorable-mention honors. His 97-yard kickoff return for a touchdown against Washington State University was the fourth-longest in school history. He collected 31 kickoff returns for a 23.5-yard average.
In track, he was voted the Pac-10's Outstanding Male Performer at the conference track championships in 1989 and 1990, winning the 100 and 200 metres. He was also a member of the Wildcats 400-meter relay team that finished second in the 1989 NCAA Championships. His college-best time was 10.17 in the 100 metres.
In 1991, he did not enroll at the school so he could concentrate on his track career. He declared for the NFL Draft in 1992.
In 2013, he was inducted into the University of Arizona Sports Hall of Fame.
At the 1992 NFL Scouting Combine, Bates ran a 4.4 40, a full tenth of a second faster than top RB prospect Vaughn Dunbar and almost 2 tenths of a second than any of the other 34 halfbacks tested. Bates was selected by the Seattle Seahawks in the 6th round (150th overall) of the 1992 NFL Draft. Because of contract negotiations, he did not sign with Seattle and held out during the 1992 season, although the time helped him to reshape his body for football.
On March 7, 1993, he signed an incentive laden contract including a $15k workout bonus, $10k playoff percentage time bonus and over $50k in performance bonus. He was a backup wide receiver, setting a franchise team record with 22 special teams tackles and was a Pro Bowl alternate to Steve Tasker. In 1995, Bates was an exclusive rights free agent where Seattle ended up agreeing to terms with him on a 1-year $700k deal in July. After new head coach Dennis Erickson traded for Ricky Proehl and drafted Joey Galloway, Bates became expendable and was waived August 27.
On August 28, 1995, the Carolina Panthers claimed Bates off waivers only to turn around and trade him the next day to the Cleveland Browns in exchange for linebackerTravis Hill. Bates spent the last 3 games of the season on the inactive list and was not retained. On March 11, 1996, he signed as a free agent with the Panthers and began his great run of seasons with the franchise, returning 33 kicks for 998 yards, with a remarkable average of 30.2 yards per return - and one kick returned for a touchdown.
After five seasons in Carolina, Bates was let go, and the Washington Redskins signed him to a 2-year, $1.33 million contract. At the end of the season he was named a Pro Bowl alternate. He was released on March 12, 2002. On March 25, he was signed by the Carolina Panthers. His season was cut short that year, however, due to a broken right ankle he suffered in preseason against the Dallas Cowboys and was placed on the injured reserve list on August 26.
On March 31, 2003, he re-signed with Carolina but was let go in the final cut-down process for the regular season on August 31. On September 10, Bates was signed by the New York Jets, but a right-hand injury placed him on the injured reserve list on November 11, and he was later released on December 23. On December 26, he was claimed off waivers by the Dallas Cowboys for their playoff run. He was not re-signed after the season.
Bates finished with 9,154 total yards in kick returns and five kick-return touchdowns (the NFL record for kickoff return touchdowns in a career is six). He was selected to the NFL 1990s All-Decade Team.