Durante il 1959 Coleman stava vivendo un periodo di ferventi attività. Il suo ultimo disco uscito per la Contemporary era stato ''[[Tomorrow Is the Question!]]'', che per la prima volta vedeva escluso il suono del pianoforte dalla musica suonata. La mossa seguente di Coleman fu quella di ingaggiare il contrabbassista [[Charlie Haden]] – che si rivelerà nel tempo uno dei suoi più importanti collaboratori – in un gruppo con Haden, Cherry, e Higgins. (Tutti e quattro avevano suonato con Paul Bley l'anno precedente.) Poi, firmò un contratto con la [[Atlantic Records]] e pubblicò il seminale ''[[The Shape of Jazz to Come]]''. L'album, secondo il critico Steve Huey, è "un evento epocale nella genesi del jazz d'avanguardia, un profondo cambiamento di percorso musicale da parte di Coleman, e un guanto di sfida gettato nell'ambiente jazz che alcuni ancora non sono venuti a raccogliere".<ref>{{Cita web| cognome =Huey| nome =Steve| titolo =The Shape of Jazz To Come| url =http://www.allmusic.com/cg/amg.dll?p=amg&sql=Artkxikbhbb39| accesso =17 dicembre 2010| dataarchivio =13 settembre 2019| urlarchivio =https://web.archive.org/web/20190913035342/https://www.allmusic.com/?p=amg&sql=Artkxikbhbb39| urlmorto =sì}}</ref> Anche se per certi versi, il materiale presente nel disco è ancora basato sugli stilemi del [[blues]] e spesso abbastanza melodico, all'epoca le composizioni crearono sconcerto e vennero criticate per l'inusuale struttura armonica e temporale. Alcuni musicisti e parte della critica videro Coleman solo come un provocatore iconoclasta; altri invece, compreso [[Leonard Bernstein]] ed il compositore [[Virgil Thomson]], lo proclamarono un genio e un vero innovatore.<ref>{{Cita web| titolo=Ornette Coleman biography on Europe Jazz Network| url=http://www.ejn.it/mus/coleman.htm| urlmorto=sì| urlarchivio=https://web.archive.org/web/20101124200347/http://www.ejn.it/mus/coleman.htm| dataarchivio=24 novembre 2010}}</ref>
Le opinioni comunque, erano le più disparate: [[Miles Davis]] dichiarò che Coleman era solo "uno svitato" (anche se poi ritrattò il suo giudizio in seguito), [[Dizzy Gillespie]] una sera in un locale si piazzò davanti al quartetto con le braccia conserte e disse: ''«Ma state facendo sul serio??»'',<ref>{{Cita libro|nome=Cles, tipografo trentino|cognome=Mondadori|titolo=Jazz! : Come comporre una discoteca di base|url=https://www.worldcat.org/oclc/799585300|accesso=2023-05-08|data=2005|editore=Einaudi|OCLC=799585300|ISBN=88-06-17911-X}}</ref> e [[Roy Eldridge]] affermò: ''«L'ho ascoltato in tutte le maniere. L'ho ascoltato mentre ero ubriaco e quando ero completamente sobrio. Ho persino suonato con lui. Penso che ci stia solo prendendo in giro tutti».''<ref>{{Cita news | nome=Juan | cognome=Rodriguez | titolo=Ornette Coleman, jazz's free spirit | data=20 giugno 2009 | editore=The Montreal Gazette | pubblicazione =The Montreal Gazette}}</ref>