Leaving Your Body Map and its sister album are a combination of older demo material written as far back as 1997 in rearranged and re-orchestrated forms and new material, all recorded simultaneously to achieve consistency; to this end, the series of instrumental interludes, all composed purportedly in lucid dreams, are sequenced in order of appearance across both albums. Each album features cover art befitting the title of its counterpart, with Bath featuring a map to a bath tub and window in yellow, and Leaving Your Body Map featuring the tub and window in red. The band inserted clues to a hidden secret in the liner notes of the albums through a series of complex symbols; to aid listeners, they recorded and released "The Secret Song" on an MCD in 2001, with lyrics purported to explain how to unlock the hidden message. It remains unsolved.
Both albums were reissued on Dark Symphonies with bonus tracks in 2005-2006. Blood Music reissued them again in 2012 for the first time on vinyl, including a box set for the companion albums, and later "The Secret Song" MCD and a CD box set of the band's discography.