Because of time constraints, a segment called "Neverwhere Land (1996)" was deleted; in this film, this would have connected "Captain Sternn" to "B-17". The story follows the influence of the Loc-Nar upon the evolution of a planet, from the Loc-Nar landing in a body of water, influencing the rise of the industrial age, and a world war. This original story was created by Corny Cole. The original rough animatics are set to a loop of the beginning of the song "Time" by Pink Floyd. The 1996 VHS release included this segment at the beginning of the tape. On the DVD release, this segment is included within the bonus features and is dedicated "In memory of Dawn M. Cole - 1931-1985". In both released versions, the sequence is set to the music of "Passacaglia" (from Magnificat), composed and conducted by Krzysztof Penderecki.
The 1996 US home video reissue features a three-minutes animation segment not included in the original theatrical release. The Italian videocassette release only adds the new footage in the widescreen video, not in the pan-and-scan version. The UK home video version of this film includes the missing three minute sequence after this film.
The DVD version has rough cut versions of an alternate frame story. This story shows the Grimaldi (the astronaut) bringing his daughter to a carousel. The carousel has the loknar at the center and the horses are replaced by elements of the stories. When Taarna is tortured in the last sequence, the action cuts to the carousel where the girl reacts with pain. The ending is similar, with the girl becoming the new protector.
In advance work-in-progress screenings for Heavy Metal, the music for the sequence "B-17" (also known as "Gremlins") opened up with a dark and lush orchestral passage by Elmer Bernstein. But when the brilliant segment "Neverwhere Land (1996)", which was to be three minutes accompanied by a song, was decided to be deleted from the release prints and Columbia had to figure out somewhere to put this, they replaced Bernstein's opening score passage with the song.
Aired in the mid-1990s, the TNT version removes all sexual material (Harry and the woman, Den's two encounters, etc), most of the language, and the drug references during the alien abduction segment (Zeke and his partner do not snort the white powder, though Zeke still makes his 'let your hands work the controls like you're straight' line, and a still of the snorting scene is in the closing credit montage). This version has not aired in several years; this was part of TNT's 'adult animation' nights (with an edited Vampire Hunter D, Robot Carnival, and Rock 'n' Rule).