The song was released on July 15, 2013, as the lead single for their sixth studio album, Hail to the King. On July 31, 2013, a limited edition CD version of the single was released, with a live version of "Nightmare" performed at The Palace of Auburn Hills attached. The song appears in the video game Rock Band 4 and as one of the official theme songs for WrestleMania 32.
The official music video premiered on the Metal Hammer website on August 16, 2013. The video depicts the band playing together, as well as shots of the king referenced in the song. The video is in black and white and is the first to feature drummer Arin Ilejay, as well as being the first Avenged Sevenfold video to feature a drummer since the video for "Dear God", which was the last to feature drummer The Rev.