Od wczesnego okresu gra Colemana wyróżniała się także charakterystycznym dźwiękiem, którego źródłem jest m.in. używanie przez muzyka saksofonów z plastiku.
Przełom nastąpił w 1958 r., gdy zgłosił się do producenta Lestera Koeniga, aby zaoferować mu kilka swoich kompozycji do wykorzystania podczas sesji nagraniowych. Koening nie tylko zaakceptował jego kompozycje, ale również zaproponował mu nagranie albumu dla firmy Contemporary. Pierwszych nagrań płytowych Coleman dokonał więc w 1958 r. z zespołem, w skład którego wchodził m.in. Don Cherry. Nagrania ukazały się na dwóch albumach: Something Else! i Tomorrow Is the Question!
W 1959 r. Coleman i Cherry dzięki pomocy Guthera Schullera i Johna Lewisa (z Modern Jazz Quartet) wzięli udział w letnich kursach w Jazz School w Lennox. W tym samym roku Coleman podpisał kontrakt z firmą Atlantic, dla której w ciągu następnych 2 lat nagrał 6 albumów. Rozpoczął także swoje stałe występy w klubie Five Spot. Pod koniec 1962 r. koncert grupy Colemana w nowojorskiej Town Hall (z basistą Davidem Izenzonem i perkusistą Charlesem Moffetem okazał się jego wielkim tryumfemEkkehard Jost. Free Jazz Str. 46. Wtedy też muzyk na dwa lata zniknął ze sceny jazzowej. Poświęcił się całkowicie nauce gry na skrzypcach i trąbce. Ponownie powrócił do działalności muzycznej w styczniu 1965 r.