Starfire Burning Upon the Ice-Veiled Throne of Ultima Thule is Bal-Sagoth's second full-length album, released in November 1996 through Cacophonous Records. This was the last album to feature Jason Porter on bass guitar, as he was replaced by Alistair MacLatchy in December 1996. As with the first album, the band only had around two weeks to record this album. They had major problems with recording the album: the temperature in the recording studio was so consistently high that the recording equipment broke down several times; and the record company, Cacophonous Records, refused to pay for new tape reels to record on, so the band had to actually record over the first album.
The cover artwork for the album is a painting by the famed artist Joe Petagno, based on a concept by Bal-Sagoth vocalist/lyricist Byron Roberts.
In the song titled "And Lo, When the Imperium Marches Against Gul-Kothoth, then Dark Sorceries Shall Enshroud the Citadel of the Obsidian Crown", a strong synthesizer melody begins at 4:17. This melody is a variation upon the melody heard in the 1982 film Conan the Barbarian during the scene inside Thulsa Doom's stronghold, composed by Basil Poledouris. Again from the score of Conan the Barbarian, at 00:37 in the track "Recovery", the theme seems to be faithfully adapted by Bal-Sagoth in the track "In the Raven-Haunted Forests of Darkenhold, Where Shadows Reign and the Hues of Sunlight Never Dance" at 2:02. The band explains their inspiration came mainly from John Williams and Basil Poledouris' scores amongst others.
On 13 May 2016 the album was re-released by Cacophonous Records as a special edition CD featuring remastered audio, expanded lyric booklet, new sleeve notes and exclusive new artwork.