Although it is often reported that Coltrane and Hartman had known each other since their days playing with Dizzy Gillespie's band in the late 1940s, the truth is that their time in the band never overlapped. Coltrane might have heard Hartman sing at a 1950 Apollo Theater performance at which they shared the stage. Hartman is the only vocalist with whom the saxophonist would record as a leader. Initially when producer Bob Thiele approached Hartman with Coltrane's request that the two record together Hartman was hesitant as he did not consider himself a jazz singer and did not think he and Coltrane would complement one another musically. However, Thiele encouraged Hartman to go see Coltrane perform at Birdland in New York City to see if something could be worked out. Hartman did so, and after the club closed he, Coltrane and Coltrane's pianist, McCoy Tyner, went over some songs together. On March 7, 1963, Coltrane and Hartman had decided on 10 songs for the record album, but en route to the studio they heard Nat King Cole on the radio performing "Lush Life", and Hartman immediately decided that song had to be included in their album.
The recording was made on March 7, 1963 at the Van Gelder Studio in Englewood Cliffs, New Jersey. Hartman once said that each song was done in only one take, except for "You Are Too Beautiful", which required two takes because Elvin Jones dropped one of his drumsticks during the first take. In 2005, the raw tapes were reviewed by jazz archivist Barry Kernfeld, who documented there were actually complete alternate takes for all six songs that he considered "absolutely riveting." Until clear ownership of these tapes is established between the Coltrane family and Universal Music, there are no plans for their release.