Deep Song is Kurt Rosenwinkel's sixth album as a band leader. The album features a new band, composed of pianist Brad Mehldau, tenor saxophonist Joshua Redman, bassist Larry Grenadier, and drummers Ali Jackson and Jeff Ballard. While the all-star cast appearing on the record was seen as an attempt at commercial success, the players had all previously worked together and were part of the underground jazz scene in New York City during the 1990s. Among the tracks on Deep Song are two jazz standards, "If I Should Lose You" and "Deep Song". Of the eight original compositions on Deep Song, three were previously recorded and appeared on The Next Step and The Enemies of Energy.