The album was recorded during Adderley's membership in the Miles Davis Sextet of 1958, and it also marks one of the few recordings Miles Davis made as a sideman after 1955. Indeed, Davis plays several of the first solos, composed the bluesy title track and, according to the liner notes, chose most of the material. "Autumn Leaves" would remain in the Davis book, and "Love for Sale" would be recorded by the Davis Sextet a little over two months later.
The twelve-bar blues "One for Daddy-O" was written by Adderley's brother Nat for Chicago radio DJ Holmes "Daddy-O" Daylie. At the end of that track, Davis can be heard addressing producer Alfred Lion, saying "is that what you wanted, Alfred?" Adderley and Davis would also be heard together on the 1958 Columbia Records release Milestones, as well as the 1959 landmark Kind of Blue, one of the most universally acclaimed jazz albums.
On March 9, 1999, the album was released on compact disc as part of the Blue Note Rudy Van Gelder Editions series, all titles in the series remastered by Van Gelder himself. It included a bonus track entitled "Bangoon" or, originally and incorrectly, "Alison's Uncle," composed by pianist Hank Jones. More hard bop in tone than the rest of the record, the original title refers to the fact that the session took place shortly after Nat Adderley's daughter Alison, had been born, hence making Cannonball "Alison's Uncle."