razem ze swoim triem.
W Cherrym Coleman znalazł partnera muzycznego, z którym na przełomie lat 50. i 60. nagrał kilka płyt uważanych obecnie za przełomowe. Wtedy też przejawiło się upodobanie Colemana do składów określanych jako „podwójne tria” lub „podwójne kwartety”, ze zdwojoną obsadą instrumentów. W 1960 r. „podwójny kwartet” w składzie: Coleman (saksofon altowy), Eric Dolphy (klarnet basowy), Cherry, Freddie Hubbard (trąbki), Charlie Haden, Scott LaFaro (kontrabasy), Ed Blackwell i Billy Higgins (zestawy perkusyjne) nagrał płytę pt. Free Jazz: A Collective Improvisation, będącą w zasadzie zapisem czterdziestominutowej kolektywnej improwizacji. Od tytułu tej płyty wziął następnie nazwę kierunek muzyczny znany jako free jazz.
Począwszy od wczesnych lat 60. muzyka Colemana zaczęła zdobywać popularność i wywierać wpływ na innych muzyków, takich jak John Coltrane, Albert Ayler i wielu innych. Równocześnie działalność Colemana wywoływała ożywione dyskusje, a sam muzyk przez niektórych uważany był za geniusza, zaś przez innych za hochsztaplera.