His recording debut as a leader occurred three years later, around the time he started to become better known as an accompanist to singer Dinah Washington, and as a member of trumpeter Dizzy Gillespie's band.

This progress was interrupted by two years in the United States Army, after which Kelly worked again with Washington and Gillespie, and played with other leaders.

Over the next few years, these included instrumentalists Cannonball Adderley, John Coltrane, Hank Mobley, Wes Montgomery, and Sonny Rollins, and vocalists Betty Carter, Billie Holiday, and Abbey Lincoln.

Kelly attracted the most attention as part of Miles Davis' band from 1959, including an appearance on the trumpeter's Kind of Blue, often mentioned as the best-selling jazz album ever.

[7] In his local area, he played with brothers Lee and Ray Abrams, as well as Ahmed Abdul-Malik, Ernie Henry, and Cecil Payne, who went on to have careers in jazz.

[8][9] Kelly made his recording debut aged 16, playing on saxophonist Hal Singer's 1948 "Cornbread",[10] which became a Billboard R&B chart-topping hit.

[9][15] Critic Scott Yanow indicates that, at this stage of his career, Kelly's main influence was Bud Powell, but that his playing "displayed some of the joy of Teddy Wilson's style along with his own chord voicings".

[18] He recruited fellow draftee and future jazz pianist Duke Pearson into the show; together they were able to convince their unit to involve more black musicians, as they were initially the only two out of around two dozen performers.

[30] Later that year, Kelly made a rare appearance playing bass, for one track of vocalist Abbey Lincoln's That's Him!, after the regular bassist, Paul Chambers, became drunk and fell asleep in the studio.

[30] Kelly also played organ on one track of Pepper Adams and Jimmy Knepper's The Pepper-Knepper Quintet, an unusual departure from his usual instrument.

[9][34] Adderley, the alto saxophonist in the band, related how Kelly came to replace Red Garland on piano: Davis had admired Kelly's playing as part of Gillespie's band, and Garland was invariably late to arrive for their club performances: "One night, Wynton was there when we started and Miles asked him to sit in.

"[35] Kelly stayed with the trumpeter until March 1963,[9] appearing on the studio albums Kind of Blue and Someday My Prince Will Come, as well as on numerous concert recordings.

[44] When Adderley left Davis in late 1959,[45] he attempted to recruit Kelly; although the pianist declined, he did participate in more recording sessions led by his former bandmate,[46] as well as more with Griffin, Mobley, Morgan, and numerous others.

[30] In May 1964, the calypso[50] track "Little Tracy" from Kelly's Verve album Comin' in the Back Door reached number 38 on Billboard's R&B chart.

[52][53] In the summer of 1965, they joined Montgomery on a tour of the US that included an appearance at the Newport Jazz Festival, and a club recording released as the Kelly co-led Smokin' at the Half Note.

[30] According to Cobb, he took charge of the financial side of the trio, as well as its recruiting of additional members, while Kelly primarily was pianist and responsible for dealing with interviewers.

[63] Bassist Bill Crow reported that Kelly was "full of fun" and said: "He was often the center of backstage laughing sessions as we told stories on each other.

While on stage, if he saw some of us standing in the wings listening, he would turn around so the audience couldn't see, give us a stern look, and drop his upper plate forward onto his lower lip, creating a grotesquely comical effect.

"[64] Kelly played "with a crisp, leaping rhythmic blues approach that generated intense excitement", wrote The Washington Post's obituarist.

[55] The Rough Guide to Jazz stated that Kelly "combined boppish lines and bluesy interpolations, but with a taut sense of timing quite unlike anyone else except his many imitators", and highlighted the effectiveness of his block chords in contributing to a "dynamic and driving accompanying style".

[9] Pianist Brad Mehldau commented that Kelly "dotted his eighth notes quite strongly, and in his own hands the effect was exhilarating".

[66] Several commentators have rated Kelly the best accompanist in jazz, including critic Ray Comiskey and music educator Mark Levine.

"[22] Pianist Bruce Barth pointed out that part of Kelly's success as an accompanist came from "occasional and compelling use of 'blues licks' and melodic phrases in place of chords.