Lewis attended O. Perry Walker High School in New Orleans, Louisiana and was schoolmates (and teammates) with NFLwide receiverMike Wallace. He was a three-year starter for head coach Terry Wilson. He made 75 tackles as a senior with four quarterback sacks and seven interceptions, also returned five punts for 180 yards and five kickoffs for 150 yards in 2003. Was named first team all-metro and all-league as a senior. He recorded 71 tackles as a junior (with two interceptions) and 54 tackles as a sophomore.
Lewis played for Oregon State between 2004-2008. After redshirting as a freshman in 2004, he started all 11 games and ended the year with 98 tackles, fourth on the team in 2005. He led the team for pass breakups with 11. He made the College Football News Third Team Freshman All-American and honorable mention by the Sporting News. In 2006, Lewis made 22 tackles for the season, was second on the team with eight pass breakups, and also accounted for a sack and two TFLs. Lewis finished off his career as one of the most physical corners in the, then, Pac-10 conference.