Steve Coleman grew up in the historically black South Side of Chicago, where music was "around all the time", just "part of the community" and "the sound of everything else". As a child, he was "in these little singing groups, imitating the Jackson 5, singing in church or something like that". He started playing alto saxophone at the age of 14. According to Coleman, his father, who he described as "a Charlie Parker nut", urged him in the jazz direction, but Coleman, who had already taken an interest in the playing of James Brown's altoist, Maceo Parker, had instead joined a funk band. But about three years later he began to study the music of Charlie Parker, Sonny Rollins, and John Coltrane.
After spending two years at Illinois Wesleyan University, Coleman transferred to Roosevelt University (Chicago Musical College) in downtown Chicago in order to concentrate on Chicago's musical nightlife. Coleman had been introduced to Chicago saxophonists Von Freeman and Bunky Green and others from whom he learned. He said, "When I was growing up and playing in Von Freeman's sessions, there were certain things that were important: Your sound, your groove, and how you express yourself....There was always this criticism for not having a sound, not having a good groove, a lot of criticism on rhythm: This cat can't swing, he has no feel, etc. So, it's...a matter of learning this particular idiom from these masters who came before you. You have to get with what it is they're good at expressing. How to make it feel a certain way, how to blend, how to swing? You get cats talking about floating the rhythm, swinging the rhythm, and all these different terms". Coleman also was in contact with Sonny Stitt, whom he regards as one of the "cats like Sonny Rollins, Coltrane, Bird ...on that same level". In addition to Freeman and others, Stitt was Coleman's connection to the era of great players like Charlie Parker.
In order to open up new opportunities for further developments, Coleman moved to New York in 1978 where he got, among other things, the experience of playing in big bands (in the Thad Jones/Mel Lewis Orchestra, Slide Hampton's big band, Sam Rivers' Studio Rivbea Orchestra, briefly in Cecil Taylor's big band, and in several other big bands). He found out that "there is a certain discipline that you get, especially a phrasing thing and learning how to play with large groups of people in a group. That carries over to what you do with a smaller group". Soon he began cutting records as a sideman with well-known figures like David Murray, Doug Hammond, Dave Holland, Mike Brecker and Abbey Lincoln. For the first four years in New York Coleman spent a good deal of time playing in the streets and in tiny clubs with a band that he put together with trumpeter Graham Haynes, the group that would evolve into the ensemble Steve Coleman and Five Elements that would serve as the main ensemble for Coleman's activities. In this group, he developed his concept of improvisation within nested looping structures. Coleman collaborated with other young African-American musicians such as Cassandra Wilson and Greg Osby, and they founded the so-called M-Base movement.
Steve Coleman said that Charlie Parker has been "probably my biggest influence". John Coltrane became a prototype to him too, in terms of his music as well as his approach and his further development. Coleman explained: "Charlie Parker, for me, was a extremely sophisticated blues player. He had a very sophisticated way of expressing the blues. It was like a ...'space blues'...very high science. And John Coltrane, for me, carried this more foreword into ...I want to use the word "world music" but . ...John Coltrane wanted to do a kind of universal music, a music of all the people. And this idea influenced me a lot." Among the living musicians in Coleman's early days, Von Freeman influenced him most as an improviser, Sam Rivers influenced him most compositionally, and Doug Hammond was especially important to his conceptual thinking. But many other musicians influenced him too. West African music (from Guinea coast; with its complex interlocked patterns) has been another huge influence on him since the late 1970s. This interest brought him in contact with ways of thinking in traditional non-western cultures which he began to study in the 1980s. Coleman was also inspired by natural things like flight patterns of bees and certainly there was the influence from the African-American popular music Coleman heard in his youth, especially from James Brown. In the course of his career, many more influences have been added.
In 1985 Coleman got the chance for his first recording as a leader (released by the German label JMT) and from then on he has recorded extensively (until 2003, since then less frequently). He also had a rather tight touring schedule that included mainly tours through Europe (e.g. averagely about 50 concerts per year in Europe in the time from 1995 to 1999).
Coleman regards the music tradition he is coming from as African Diasporan culture with essential African retentions, especially a certain kind of sensibility. He searched for these roots and their connections of contemporary African-American music. For that purpose, he travelled to Ghana at the end of 1993 and came in contact with (among others) the Dagomba (Dagbon) people whose traditional drum music uses very complex polyrhythm and a drum language that allows sophisticated speaking through music (described and recorded by John Miller Chernoff). Thus, Coleman was animated to think about the role of music and the transmission of information in non-western cultures. He wanted to collaborate with musicians who were involved in traditions which come out of West Africa. One of his main interests was the Yoruba tradition (predominantly out of western Nigeria) which is one of the Ancient African Religions underlying Santería (Cuba and Puerto Rico), Vodou (Haiti) and Candomblé (Bahia, Brazil). In Cuba, Coleman found the group Afrocuba de Matanzas who specialized in preserving various styles of rumba as well as all in Cuba persisting African traditions which are mixed together under the general title of Santería (Abakua, Arara, Congo, Yoruba). In 1996 Coleman along with a group of 10 musicians as well as dancers and the group Afrocuba de Matanzas worked together for 12 days, performed at the Havana Jazz Festival, and recorded the album The Sign and the Seal. In 1997 Coleman took a group of musicians from America and Cuba to Senegal to collaborate and participate in musical and cultural exchanges with the musicians of the local Senegalese group Sing Sing Rhythm. He also led his group Five Elements to the south of India in 1998 to participate in a cultural exchange with different musicians in the carnatic music tradition.
The French computer-music research centre IRCAM offered Coleman to further develop his ideas in the form of interactive computer software at the IRCAM facilities in Paris with the aid of programmers and IRCAM technology. A concert in June 1999 featuring Coleman's group interacting with what he calls his Rameses 2000 computer software program was the public result of this commission. However, there are no official recordings of this singular project available.