Barnes attended the Delaware State University where he rushed for 1336 yards in 1988 and 3282 during his college career. He was not drafted by the NFL, but signed as a free agent with the New York Jets in 1989 where he spent the entire season on the practice squad.
He came to Canada in 1990, and made an immediate impression with the Ottawa Rough Riders. He rushed for 1260 yards and 5 touchdowns on his way to winning the CFL's Most Outstanding Rookie Award. An interesting fact is that CFL legend and Ottawa quarterback Damon Allen also rushed for 1,000 yards that year. Barnes proved his rookie season was no fluke by setting a team rushing record, posting an incredible 1,486 yards rushing in 1991 and 10 rushing touchdowns it would be his finest season as Ottawa finished 7-11 that year. Barnes also played with Shreveport Pirates, Hamilton Tiger-Cats and Toronto Argonauts but ended his career in 1996 with Ottawa the last season for the Rough Riders. A fitting end for one of the last crowd favorites as a Rough Rider.