"Holy Grail", along with another track from Magna Carta... Holy Grail called "Oceans" were recorded in 2011 during the recording sessions for Jay-Z's collaborative album with Kanye West, Watch the Throne. West wanted the two songs to appear on Watch the Throne, but Jay-Z chose to keep them for his upcoming studio album and they were replaced with "No Church in the Wild" and "Made in America". The early version of the instrumental was created in 2011 by The-Dream. When the recording sessions for MCHG started, Timbaland together with fellow producer J-Roc rearranged it to create the final track.
"Holy Grail" is composed in a D minor key, and plays in common time at a tempo of 72 beats per minute. The vocals ranges from a G3 to C6. Jay-Z lyrically sampled rock group Nirvana's single "Smells Like Teen Spirit", after receiving permission from Courtney Love who owns the rights to the original song. In an interview with BBC Radio 1, Jay-Z stated that "Holy Grail" was "the map for the album" and that it set the tone for the rest of MCHG. When the song was first recorded for Watch the Throne Jay-Z thought it would get lost on the album and decided to keep it as the "center piece" for his next album. The song's lyrics can be interpreted as Jay-Z's and Timberlake's love-hate relationship with fame.
On August 2, 2013, Jay-Z revealed to Power 106 that he and fellow tour mate Justin Timberlake had begun shooting the music video for "Holy Grail". The music video was directed by Anthony Mandler and was released on August 29, 2013 on Facebook, making social media history as the first time a clip from major artists debuted strictly on the site. Dubbed a "visual" rather than a "music video", the piece is a remixed version of the original album version, featuring pitch shifted vocals and a change in the song structure. The visual was critically acclaimed for both its imagery, and remixed vocals. Kyle Anderson from Entertainment Weekly praised the piece's imagery, describing its nightmarish sequences as "arresting", and complimented the remixed video version of the song which he thought was "miles beyond the album version".
"Holy Grail" has received mixed reviews from critics. Andy Gill of The Independent described the song as "smooth and mellifluous," while Rolling Stone's Simon Vozick called it a "surprisingly moody opener." DJ Booth praised the track as an "appropriately bombastic intro to an epic LP." Panning the song as "laughably overblown", Ian Cohen of Pitchfork Media writes that Timberlake "cycles through every tortured artist cliché short of a crucifixion metaphor." Cohen further stated that the "Smells Like Teen Spirit" interpolation "becomes just another forgettable status symbol" and commented: "Where Kurt Cobain felt compromised by his fame, Jay and Timberlake are doing everything in their power not to offend the money people—whether it's Samsung, Target, or someone dropping $250 to see them at the Rose Bowl."
The song had a hot-shot debut on many charts upon the release of the album, despite not being released as an official single. It debuted at number eight on the US Billboard Hot 100, being at the time the second highest debut on that chart of the year. It peaked at number four and remained in the top 10 for 16 weeks. It has sold over 3 million copies in the US as of March 2014.
"Holy Grail" was performed during the On the Run Tour (2014), a co-headlining tour by Beyoncé and Jay-Z. During the performance of the song, Justin Timberlake's vocals were replaced by Beyoncé's. Consequence of Sound's Alex Young chose the song as one of the particular highlights of the show.