After that McCoy moved to New York and that marked the beginning of his professional involvement in jazz. As the first pianist in Jazztet, group led by Benny Golson and Art Farmer, he participated in Meet the Jazztet on Argo label. The recording was a commercial and critical success.
During 1960-65 he was pianist in John Coltrane Quartet accompanied with drummer Elvin Jones and bassist Jimmy Garrison. He participated on all major recordings of Quartet, but also recorded his own records for Impulse! label. He continued recording for Blue Note after leaving Quartet. McCoy recorded his first album as a leader in 1963; it was a trio with Jones and Art Davis, called Inception.
McCoy and Jones left John Coltrane Quartet unsatisfied with arrival of new musicians in group, such as Pharoah Sanders (who came in for Eric Dolphy) and Rashid Ali, free-jazz drummer often in conflict with Jones.
Until 1970 McCoy continued to record for Blue Note with musicians such as Lee Morgan, Joe Henderson, Wayne Shorter, Bobby Hutcherson, Alice Coltrane and Gary Bartz. He had some hard times for two years, during which he drove a cab for some time and played with Ike and Tina Turner, mostly rhythm and blues.