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.
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