Одна из самых замечательных записей выступления в клубе была сделана женой Колтрейна Наимой. Пластинка получила название «The Thelonious Monk Quartet. Live at the Five Spot: Discovery!». Этот альбом долго оставался единственной записью совместного выступления двух джазовых гигантов, пока в недрах Библиотеки Конгресса США не обнаружили еще одну пленку, на которой был записан блестящий концерт квартета Телониуса Монка с Джоном Колтрейном в ноябре 1957 г. в знаменитом «Carnegie Hall». Спустя почти пять десятилетий, в 2005 г., пластинка вышла полумиллионным тиражом и стала важнейшим событием в джазовом мире.
В 1958 г. эксцентричный Монк распустил свой квартет, и Колтрейн возвратился к Майлзу Дэвису, который под влиянием Джорджа Рассела
теперь экспериментировалУвлечение Майлза Дэвиса модальным джазом принесло изумительные плоды: был записан альбом «Kind of Blue», соло на саксофоне — в исполнении Джона Колтрейна. Затем, в 1960 г., был записан альбом «Giant Steps», в котором квартет исполнял композиции только самого Колтрейна. Эта пластинка явилась своего рода манифестом, провозгласившим переход к новому направлению в джазе. Нью-йоркский клуб «Five Spot» уже в конце 1959 г. явился местом, где были сотрясены основы джаза. Именно в это время здесь выступал саксофонист Орнетт Коулмен
со своим квартетом. Коулмен проповедовал ничем не ограниченную мелодическую импровизацию (поэтому и название эти эксперименты получили «фри-джаз»). Многих музыкантов и слушателей такая музыка отталкивала, приводила в недоумение, но некоторые критики мгновенно провозгласили Орнетта Коулмена новым мессией. Удивительным образом фри-джаз соответствовал тем настроениям, которые давно зрели в сегрегированном американском обществе. Джон Колтрейн как раз был поглощен поисками свободы в своей музыке.Но для осуществления музыкальных идей Колтрейну требовался новый ансамбль. И после гастролей по Европе с комбо Майлза Дэвиса Колтрейн решает создать свой квартет. Однако найти нужных музыкантов было не так просто: кто-то из музыкантов не мог нарушить ранее подписанные контракты, а кто-то просто не дотягивал до уровня требуемого мастерства. Сам же Колтрейн непрерывно развивался как музыкант: осваивал не совсем популярный у джазменов сопрано-саксофон, на котором еще в 1930—1940-е гг. блестяще играл Сидней Беше. Джон говорил, что у себя в душе он слышал музыку, которую можно было передать только сопрано-саксофоном. К 1960 г. сформировался основной состав «классического квартета» Джона Колтрейна: саксофон — Колтрейн,
барабаны — Элвин Джонс (1927—2004), фортепиано — Маккой Тайнер (род. 1938), контрабас — Джимми Гаррисон (1934—1976). И все же Колтрейн считал, что его музыканты еще не совсем готовы к осуществлению его идеи записать музыку Орнетта Коулмена, которой Джон был буквально захвачен. Поэтому он записал альбом John Coltrane & Don Cherry «The Avant-Garde» с музыкантами ансамбля самого Орнетта Коулмена. На этой пластинке Джон впервые играл на сопрано-саксофоне.С 1960 г. Колтрейн записал со своими музыкантами на фирме «Atlantic» десять альбомов, первый из которых назывался «Africa/Brass», а самым популярным альбомом этого периода становится «My Favorite Things». Основной темой этой пластинки была мелодия песенки из мюзикла «Sounds of Music» Ричарда Роджерса. Джазмен сыграл роджеровскую мелодию, превратив ее в настоящий шедевр именно на сопрано-саксофоне. Колтрейн в своей музыке был часто ориентирован на песенный язык, приправляя изначально простую мелодию сложной и дерзкой гармонией. Но свои лучшие пластинки Джон Колтрейн запишет в период с 1961 по 1967 г. с новым лейблом «Impulse!». Продюсер записывающей фирмы, понимая значимость джазмена, предоставил музыканту возможность записывать столько пластинок, сколько тот сочтет нужным. Это был исключительный случай, ведь чаще всего фирмы, нацеленные на коммерческий успех, диктовали музыкантам свои условия. В этот период творчества Колтрейн становится такой же культовой фигурой, каким в 40-50-е гг. XX в. был Чарли Паркер.