A través de Billy Higgins, Cherry conoció a Ornette Coleman en 1957, y bajo las órdenes de Paul Bley formaron un quinteto junto con Charlie Haden.

Cherry fue muy criticado (inicialmente también por Miles Davis) por sus improvisaciones fracturadas y puntillistas, sin embargo, terminaría por ejercer gran influencia entre los músicos jóvenes de los años sesenta.

En 1963, codirigió con Archie Shepp el New York Contemporary Five; después, en Europa, dirigió su propia banda, en la que trabajó Gato Barbieri, recién llegado de Argentina.

En sus últimos años, Cherry se inclinó al estudio de las llamadas músicas del mundo y la etnomusicología en general, uniéndose musicalmente a Collin Walcott y Naná Vasconcelos con quienes formó la agrupación Codona.

También probó suerte en el rock y el funk, y formó parte del grupo Old and New Dreams, cuarteto compuesto con antiguos integrantes de la banda de Coleman, entre los que estaba el saxofón Dewey Redman.