It was released in Australia in November 2004 by Metal Warriors and in Japan at the same time by Sound Holic.

[1] Unlike the albums that preceded and followed it, One Step Beyond featured the same artwork and track-listing in all markets where it was released (although the United States version has a different running order).

The Australian version was to contain covers of "Til the Living End" by Dokken and Queen's "The Hero" but Dungeon's German label LMP refused to allow them to issue an alternate edition and the tracks were later made available as downloads.

LMP later issued a special edition for the US market that also included the band's self-produced 2004 live DVD.

The band photos in the CD booklet feature Lord Tim and Stu Marshall with new drummer Grahame Goode and former bass player Justin Sayers, who had left the group in 1999.