Blue and Someday My Prince Will Come, as well as on numerous concert recordings. On Kind of Blue (1959), often mentioned as the best-selling jazz album ever, Kelly played on the track "Freddie Freeloader". Even though Kelly was Davis' regular pianist at the time, the trumpeter had planned the album with Bill Evans in mind, so this is the only piece on which Kelly appears. Kelly toured 22 cities in Europe as part of Davis' quintet in the spring of 1960. Fellow pianist McCoy Tyner commented on Kelly's playing with Davis: "His harmonic colorations were very beautiful. But I think above all it was his ability to swing. John [Coltrane] used to mention that. Miles used to get off the bandstand and just look at Wynton with admiration, because he really held the group together." Davis often left considerable time between band engagements, which allowed the musicians to do other work, so Kelly continued to record with other leaders, including with other members of the Davis band. In February 1959, when in Chicago for performances with Davis, Kelly was pianist on Cannonball Adderley Quintet in Chicago, and bassist Chambers' Go. Later that year, Kelly made his first album for Vee-Jay Records, in a quintet containing Wayne Shorter; Kelly returned the favor a few months later by playing on the saxophonist's debut as leader, Introducing Wayne Shorter. Kelly also recorded with Coltrane, including for one track, "Naima", from the saxophonist's Giant Steps. When Adderley left Davis in late 1959, he attempted to recruit Kelly; although the pianist declined, he did participate in more recording sessions led by his former bandmate, as well as more with Griffin, Mobley, Morgan, and numerous others. Kelly made his first recording with guitarist Wes Montgomery in 1961; they then made Full House the next year; the pairing was described by The Penguin Guide to Jazz as "an association that promised a lot and delivered more". When he left Davis, Kelly formed his own trio with two others leaving the trumpeter – Chambers and drummer Jimmy Cobb. They soon embarked on a national tour and had recording dates with Verve Records, Kelly having left Vee-Jay after four albums. In May 1964, the calypso track "Little Tracy" from Kelly's Verve album Comin' in the Back Door reached number 38 on Billboards R&B chart. A few months later, the trio toured Japan for a series of George Wein-organized concerts.