He played college football and ran track for the University of Arizona. 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-meter dashes. 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 meters.
At the June 1992 Olympic Trials he finished third, qualifying for the Olympics, edging Carl Lewis by one one-hundredth of a second for the final qualifying spot. In the 1992 Barcelona Olympics, his time of 20.38 from the inside lane, put him 0.37 seconds behind gold medal winner Michael Marsh and 0.25 seconds behind silver medalist Frankie Fredericks to win the bronze medal. He set his personal best time in the 200-meter dash was 20.01 seconds, set at the Weltklasse meet in Zurich 13 days after the Olympics.
He was the 150th overall selection by the Seattle Seahawks in the 1992 NFL Draft, but only joined the team in 1993, after the Olympics were over. In his football career, the majority of which he played for the Carolina Panthers, he had 9,110 total yards in kick returns and five kick-return touchdowns (the NFL record for kickoff return touchdowns in a career is six). In one of his best seasons, 1996, he returned 33 kicks for 998 yards - a remarkable average of 30.2 yards per return - and one kick return touchdown. Bates was selected to the NFL 1990s All-Decade Team.