The album had its genesis in a conceptual story apparently written for Johnny Cash. Costello himself states:
The Delivery Man started out as a story about the impact on three woman’s lives of a man with a hidden past. The story took the song "Hidden Shame" as its unsung prelude. Parts of the narrative ended up being displaced from the final album by more urgent songs taken from the news headlines. One of the songs moved aside was to find an ideal home on Secret, Profane & Sugarcane.
Shortly after its release, Lost Highway issued a deluxe edition of the album, including a bonus disc containing seven tracks from the Clarksdale Sessions ten-inch vinyl record, a collection of songs recorded live at Delta Recording in Clarksdale, Mississippi. The Clarksdale Sessions, subtitled "Delivery Man Companion," contained new versions of tracks from the proper album as well as an unreleased Costello original "In Another Room," and covers of the Bartholomew original "The Monkey" and "Dark End of the Street." Tom Waits has named it one of his favourite albums.