After college, Stewart moved to New York where he quickly built his reputation, first gaining wider recognition in John Scofield's quartet with pianist Michael Eckroth and bassist Ben Street and in a trio with Larry Goldings and Peter Bernstein, which has become the longest-running group Stewart has played with, having begun in 1989 and continuing to this day, however infrequently the group may be found in performance. Stewart's musical horizons expanded when funk saxophonist Maceo Parker tapped the budding drummer upon seeing him with Larry Goldings at a regular gig at a club in Manhattan. Stewart worked with Parker from 1990 to 1991, touring and recording on three of Parker's albums. The association led to Stewart's gig with James Brown, who told Stewart that there "Ain't no funk in Iowa!" upon learning the drummer's roots. Another close associate is pianist Kevin Hays, with whom he performs, along with fellow WPC graduate, bassist Doug Weiss. The Kevin Hays trio has recorded five CDs and toured internationally. Musical associations with Lee Konitz, Michael Brecker, Pat Metheny and many other notable jazz musicians have followed.