Steve began playing music just days before his 14th birthday as a freshman at South Shore High School on the south side of Chicago. His first instrument was violin but later that year he switched to the alto saxophone. For three years Steve studied the basics of music and saxophone technique, then he decided that he wanted to learn how to improvise. Looking for the best improvising musicians to listen to is what brought Steve to the music of Charlie Parker, although it helped that his father listened to Parker all the time. After spending two years at Illinois Wesleyan University Steve transferred to Roosevelt University (Chicago Music College) in downtown Chicago in order to concentrate on Chicago's musical nightlife. Specifically Coleman had been introduced to the improvisations of Chicago premier saxophonists Von Freeman, Bunky Green, Gido Sinclair, Sonny Greer and others and he wanted to hang out and learn from these veterans. By the time he left Chicago in May 1978, he was holding down a decent gig leading a band at the New Apartment Lounge, writing music, playing Parker classics, and getting increasingly dissatisfied with what he felt was a creative dead end in the Chicago scene.
After hearing groups from New York led by masters like Max Roach, Art Blakey, Woody Shaw, The Thad Jones-Mel Lewis Orchestra, Sonny Rollins, etc. come through Chicago with bands that featured great players with advanced musical conceptions, Steve knew where he wanted to go next. He felt he needed to be around this kind of atmosphere in order to grow musically.
Hitchhiking to New York and staying at a YMCA in Manhattan for a few months, he scuffled until he picked up a gig with the Thad Jones-Mel Lewis Big Band, which led to stints with the Sam Rivers Big Band, Cecil Taylor's Big Band and others. Soon he begun cutting records as a sideman with those leaders as well as pivotal figures like David Murray, Doug Hammond, Dave Holland, Mike Brecker and Abbey Lincoln. However it was really the influence of Von Freeman and Bunky Green in Chicago, Thad Jones, Sam Rivers, Doug Hammond in New York and listening to recordings of past improvising masters and music from West Africa that got Coleman turned around musically. . The most important influences on his music at this time was listening to tenor saxophonist Von Freeman (who primarily influenced Coleman as an improviser), saxophonist Sam Rivers (who influenced Steve compositionally) and drummer/composer Doug Hammond (who was especially important in Steve's conceptual thinking).