Wtedy też po raz pierwszy zwrócili na niego uwagę muzyczni krytycy.
W 1957 rozpoczął współpracę z Theloniousem Monkiem. Kilka miesięcy wspólnego grania było niezwykle korzystne dla rozwoju stylu Coltrane’a – Monk nauczył go grać dwa lub nawet trzy tony równocześnie oraz pomagał mu w jego poszukiwaniach harmonicznych. Ponowna (od 1958) kooperacja z Davisem zaowocowała nagraniem jednej z najwybitniejszych płyt w historii jazzu Kind of Blue (1959). O ile wcześniej Davis był zainteresowany – tak jak i Coltrane – rozwijaniem wieloakordowych struktur, tak w tym okresie zdecydowanie ograniczył liczbę akordów, a jego zainteresowanie przeniosło się w stronę melodyczną utworów. Również i Coltrane poszedł w tym samym kierunku, gdyż dawało to więcej możliwości do swobodnie prowadzonych partii solowych. Ten sposób grania wyraźnie uwidocznił się na albumie Kind of Blue, zwłaszcza w takich utworach jak „So What” i „Flamenco Sketches”. Oba te utwory są doskonałymi przykładami modalnej gry muzyków. Również klasyczne 12-taktowe bluesy „All Blues” i „Freddie Freeloader” mają wyraźny rys tego modalnego grania – nie ma w nich żadnych harmonicznych dodatków w rodzaju np. akordów zastępczych itd., a jest tylko prosty wzór bluesowy trzech czterotaktowych sekwencji. Jak sam powiedział w 1960 „Mogłem grać trzy akordy na jeden [Davisa].