Hancock's first version was recorded in a hard bop style, featuring solos by trumpeter Freddie Hubbard and saxophonist Dexter Gordon.

[5] Hancock joined bassist Butch Warren and drummer Billy Higgins in the rhythm section, with Freddie Hubbard on trumpet and Dexter Gordon on tenor saxophone.

[6] After pianist Chick Corea left Afro-Cuban jazz percussionist Mongo Santamaría's band, Hancock served as a temporary replacement for a weekend engagement at a nightclub in The Bronx.

On December 17, 1962, he recorded a three-minute version, suitable for radio, where he joined timbalero Francisco "Kako" Baster in a cha-cha beat, while drummer Ray Lucas performed a backbeat.

[11] Hancock re-recorded "Watermelon Man" for Head Hunters (1973), combining synthesizers with a funk beat influenced by James Brown and Sly and the Family Stone,[13] adding an eight-bar section.

On the intro and outro of the tune, percussionist Bill Summers blows into beer bottles in an imitation of hindewhu, a style of singing/whistle-playing found in Pygmy music of Central Africa.

Hancock and Summers were struck by the sound, which they heard on the album The Music of the Ba-Benzélé Pygmies (1966) recorded by Simha Arom and Geneviève Taurelle.