Prior to Dystopia's recording, longtime drummer Shawn Drover and guitarist Chris Broderick announced their departure from the band.

Following the lukewarm response to Megadeth's previous album, 2013's Super Collider, Dystopia received mostly favorable reaction from critics, being considered a return to form for the band.

In May, bassist David Ellefson lost his brother Eliot to cancer, after which the band cancelled a number of scheduled shows.

[18] The band entered Latitude South Studios in Leiper's Fork, Tennessee, in April 2015,[19] and recording finished in July.

It later came to light that the band had in fact been in discussions with former members Nick Menza (drums) and Marty Friedman (guitar), but were unable to reach an agreement.

[27] During March 2015, several rock music news websites speculated that Lamb of God drummer Chris Adler would perform drums on the album,[28][29] which was later confirmed by the band.

The setting homages 12 Monkeys by having a deserted and destroyed city, Mad Max by putting Vic under the Sydney Harbour Bridge, and The Walking Dead with the "drones meant to be like Michonne’s enslaved zombie buddies".

[38][39] Mustaine also stated his belief that the album sound and songwriting would be influenced by his 2014 guest performance alongside the San Diego Symphony.

[26] It was also announced that the album would feature a guest appearance from country musician Steve Wariner, who would perform steel guitar parts.

[20] In spite of the departures of Broderick and Drover, Ellefson stated that the band initially intended to release the album late in 2015.

It was suggested that the departures of Broderick and Drover, as well as the lack of details about possible replacements fueled anticipation on the part of fans and critics.

[45] The album was released on January 22, 2016, by Mustaine's Tradecraft label, distributed by Universal Music, and was made available on CD, vinyl and digital download formats.

[50] In addition, a deluxe version was announced featuring a virtual reality headset and including a code to download video of the band performing five songs from the album.

[56] The band toured the United States with Suicidal Tendencies again in September–October 2016, with Metal Church, Amon Amarth and Butcher Babies replacing Children of Bodom and Havok.

Reviewer Ray Van Horn, Jr. proclaimed "Dystopia isn't monumental, but it's a damned good (often magnificent) album.

"[73] Thom Jurek from AllMusic agrees, saying "It's easy to appreciate the music on Dystopia; it showcases Mustaine and a crack new version of Megadeth at a creative peak.

"[62] Dom Lawson of The Guardian called the album an "absolutely blistering return" to the style "of past glories like Rust in Peace and Endgame.

[74] Metal Hammer's Dom Lawson credited band turmoil following the release of Super Collider for the creation of "one of the finest records Megadeth have ever made.

He opined that Loureiro's playing was largely "cold, calculated and emotionless," and suggested that Mustaine's lyrics form "a loose concept album of post-capitalist suspicions, X-Files conspiracies, and pseudo-Libertarian rhetoric.

Club declared that the album features "masterful instrumentation," he heavily criticized lyrics displaying Mustaine's "offensive politics" and "xenophobia,"[76] a sentiment shared by Benjamin Aspray of Slant Magazine.