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 for four weeks in December 1992 (a brief break for Christmas followed by a return to recording) and three weeks in January 1993 with producer John Leckie.
Guitarist Nick McCabe, in reflection, has said "I think something of us as a band got lost" after Storm in Heaven. "For the next ten years after that, that sensation was missing from the music for me. That was the last time we made that kind of landscape for the imagination to run about in." According to producer John Leckie, the band worked until "4 a.m. every night ... they were quite a nocturnal band ... they didn't get much sleep. They smoked a lot of dope." Drummer Pete Salisbury's percussion was inspired by Dr. John's Gris-Gris album, while the brass section from the Kick Horns on "The Sun, The Sea" and "Butterfly" was influenced by Fun House. Only three of the songs that ended up on the album had been previously played in live performances ("Slide Away", "Already There", and "The Sun, The Sea"), while the remaining seven songs were composed at Sawmills Studios in Cornwall. "Virtual World" was recorded in two versions, one with Yvette Lacey on flute (who had previously contributed her flute to "Gravity Grave") and the other with rare slide guitar from Nick McCabe. The lyrics of "Already There" were changed and developed further from their previous live performances. It is the only song by The Verve in which Richard Ashcroft and Nick McCabe collaborated on the lyrics.
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. 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.
Other songs which did not end up on the album yet were recorded during the Sawmills Studios sessions included "Shoeshine Girl", "South Pacific", "No Come Down", "Twilight", "6 O'Clock", and "Where The Geese Go". 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.
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.