The official track listing for Elysium was first announced by keyboardist Jens Johansson on the forum of the band's website on 8 November 2010.[7] The album was released on four different formats: a regular CD; a deluxe Digipak edition CD with a bonus disc containing demos of the entire album; a double-disc collector's edition CD with two bonus tracks on a 7" single; and on vinyl.[1] "Darkest Hours" and "Infernal Maze" were released as a single on 26 November 2010, reaching #4 on the Finnish singles chart.[2] At a length of 18:07, Elysium's title track is by far the longest Stratovarius song to date.
The album cover art was created by Gyula Havancsák and features the same star-shaped spacecraft from Polaris (2009).