A Storm in Heaven originated during the band's four-week stay outside of Llandudno, Wales. After the autumn 1992 Gravity Grave tour, they relocated to Sawmills Studios in Cornwall where sessions were recorded with producer John Leckie for seven weeks.
Like the band's prior EPs and singles, most of the songs on this album are bathed in heavy layers of delay (echo) and reverb, used on both the guitars and the vocals, to give a disorientingly psychedelic overall effect. The lyrics of "Butterfly" pertain directly to the so-called butterfly effect, and the song "Catching the Butterfly," from the band's 1997 album Urban Hymns, is apparently a continuation of this theme. Guitarist Nick McCabe has stated that the track was recorded at 3:00 a.m. while playing along with a Steely Dan sample. The album's closing song, "See You in the Next One (Have a Good Time)", is built on a subdued piano motif played by McCabe and atmospheric acoustic guitars played by vocalist Richard Ashcroft. After this album, the band's music moved in a less psychedelic, more structured direction, and their name was officially changed to "The Verve" for legal reasons, so as not to clash with the record label Verve Records.
Just prior to the release of the album, the track "Star Sail" appeared on the soundtrack of the 1993 film Sliver.
As with all of the band's releases, A Storm in Heaven features enigmatic artwork designed by Brian Cannon. The cover photo was shot inside Thor's Cave in Staffordshire, England. The vinyl LP version came in gatefold packaging.