After playing his college football at the University of Kentucky, Stewart joined the CFL's Calgary Stampeders for the 2001 season, playing only one game before being released the following year in the preseason.
From 2002 to 2011 Stewart played for the Montreal Alouettes, leading the team in quarterback sacks for four seasons (2003–06). In 2004 he had 21 tackles, 9 sacks and 4 interceptions (returning 2 of those for touchdowns), good enough to make the CFL All Star Team and to win the CFL's Most Outstanding Defensive Player Award. On October 12, 2009, Stewart became the Alouettes all-time sacks leader with 53 career sacks, passing Elfrid Payton who had 52. He finished with 66 career sacks in Montreal after he was released on February 8, 2012.
On October 10, 2012, Stewart again signed with the Calgary Stampeders where he recorded 4 sacks in only 4 games, bringing his career total to 70. Following the 2012 CFL season, he was released by the Stampeders. He was signed to the Alouettes' practice roster on August 13, 2013 after Montreal released Ejiro Kuale earlier in the week.