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 Anwar Stewart again signed with the Calgary Stampeders. Stewart recorded 4 sacks in only 4 games with the Stampeders, bringing his career total to 70. Following the 2012 CFL season Anwar Stewart was released by the Stampeders.