The single has two b-side tracks: A remix of "Mercy Street" (originally from Gabriel's previous studio album So, released in 1986) by William Orbit and an earlier version of the a-side. This version had originally appeared in the Wim Wenders film Until the End of the World (1991) but was not included on the officialsoundtrack.
Track listing (CD single)
All songs written by Peter Gabriel.
- "Blood of Eden (Album Version)" – 6:33
- "Mercy Street" (William Orbit mix) – 8:00
- "Blood of Eden (Special Mix for Wim Wenders' "Until the End of the World)" – 6:15