The album was recorded during Adderley's membership in the Miles Davis Sextet of 1958, and is one of the few post-1955 appearances of Miles Davis as a sideman. 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 Adderley 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."