Fletcher attended the University of Wisconsin, where he played for the Wisconsin Badgers football team from 1998 to 2000. He was a key member of the Badgers' back-to-back Rose Bowl champion teams, and remains the Badgers' all-time career interceptions record holder with 21 total interception in three seasons of college football. He was named a first-team All-American by multiple selector organizations in 1999, and was recognized as a consensus first-team All-American in 2000. He was also named to the Top 100 Greatest College Players list by America's Best & 10. Fletcher was an initiated member of Kappa Alpha Psi fraternity while he was a Wisconsin undergraduate.