Instrumen pertamanya adalah biola, tetapi kemudian tahun itu dia beralih ke saksofon alto. Selama tiga tahun, Steve mempelajari dasar-dasar musik dan teknik saksofon, lalu dia memutuskan bahwa dia ingin belajar berimprovisasi.
Pencariannya untuk menemukan musisi berimprovisasi terbaik untuk didengarkan membawa Steve ke musik Charlie Parker, meskipun bantuan dari ayahnya yang selalu mendengarkan Parker.
Setelah menghabiskan dua tahun di Universitas Illinois Wesleyan, Steve pindah ke Roosevelt University (Chicago Music College) di pusat kota Chicago untuk berkonsentrasi pada musik di kehidupan malam Chicago. Khususnya, Coleman telah diperkenalkan pada improvisasi oleh saxofon terkemuka Chicago seperti Von Freeman, Bunky Green, Gido Sinclair, Sonny Greer, dan lainnya dan dia ingin menghabiskan waktu bersama dan belajar dari para veteran ini.
Setelah mendengar grup dari New York yang dipimpin oleh master seperti Max Roach, Art Blakey, Woody Shaw, The Thad Jones-Mel Lewis Orchestra, Sonny Rollins, dan lain-lain datang ke Chicago dengan band yang menampilkan pemain hebat dengan konsepsi musik yang canggih, Steve tahu ke mana dia ingin pergi selanjutnya. Dia merasa perlu berada di sekitar atmosfer seperti ini untuk tumbuh secara musikal.
Steve Coleman menganggap tradisi musik dari mana dia berasal sebagai budaya Diaspora Afrika dengan retensi Afrika yang penting, terutama jenis sensibilitas tertentu.
Ia pun pindah ke New York tahun 1978 dan tinggal di YMCA di Manhattan selama beberapa bulan, sampai mendapatkan pekerjaan dengan Thad Jones-Mel Lewis Big Band, yang mengarah ke penugasan dengan Sam Rivers Big Band, Cecil Taylor’s Big Band, dan lain-lain.
Lalu dia mulai merekam rekaman sebagai sideman dengan para pemimpin tersebut serta tokoh-tokoh penting seperti David Murray, Doug Hammond, Dave Holland, Mike Brecker, dan Abbey Lincoln.
Namun, pengaruh terbesar pada musiknya saat ini adalah mendengarkan pemain saksofon tenor Von Freeman (yang terutama memengaruhi Coleman sebagai seorang improvisator), pemain saksofon Sam Rivers (yang memengaruhi Steve secara komposisional), dan drummer/komposer Doug Hammond (yang sangat penting dalam pemikiran konseptual Steve).
Bahkan bermain dengan para master ini hanya sebagian kecil dari cara untuk membayar sewa, dimana selama empat tahun berikutnya Coleman menghabiskan banyak waktu bermain di jalanan New York City dengan jumlah uang yang kecil dengan band jalanan yang dia buat bersama pemain trompet Graham Haynes yang kemudian kelompok ini dikenal sebagai Steve Coleman and Five Elements.
Dalam grup ini, dia mengembangkan konsep improvisasinya dalam struktur looping berpola. Coleman berkolaborasi dengan musisi Afrika-Amerika lainnya seperti Cassandra Wilson dan Greg Osby, dan mereka mendirikan gerakan yang dikenal sebagai M-Base.
Konsep M-Base yang merupakan singkatan dari “macro-basic array of structured extemporization” atau bermakna “struktur makro dasar untuk ekstemporasi terstruktur”.
Konsep M-Base mengingatkan pada energi kreatif para pencipta bebop, kolektif yang longgar, dan juga pada tujuan musikal mereka. Konsep ini tidak termasuk “jazz neo-klasik,” musik bebas tanpa struktur, musik fusi, musik yang tidak terutama diimprovisasi, atau yang dibentuk dengan mempertimbangkan aspek komersial.
