Legion is more musically ambitious than most other Deicide albums, incorporating more technical riffing and song structures. The band considers this album to be its most difficult, and claims it is too chaotic. When the Hoffman brothers quit the band, Eric Hoffman stated it is simply that Glen Benton refused to play longer sets and could not do technical riffing on his bass. Though the album has been praised by fans, "Dead But Dreaming" was the only track of this album that remained in their live set, though as recently as 2010 the band has begun playing "Trifixion" and "Holy Deception" as well. Unlike Deicide's first album, this release did not use any pitch shifters or harmonizers on Benton's vocals. However, delay, reverb, and multi tracking were among the studio manipulations used to get the vocal effects on the album.
The first track, "Satan Spawn, the Caco-Daemon", features a backward message. At about twenty seconds, a voice can be heard saying "Satan Spawn, the Caco-Daemon".
Steve Asheim said of Legion, "For Legion, I was too busy worrying about how we were going to get a second album out to really think about what it meant, I was just trying to stay in the music business and stay brutal."
A reviewer for The Metal Storm said, "in general a good album, some songs are well executed and with complex musical writing, but there are others that are just very simple and repetitive".
Vincent Jeffries of Allmusic stated, "Legion stands out as a musically complex but familiar offering from the band. Live favorite 'Trifixion' is indeed one of the better cuts from the release, but it's easier to consider this disc (and most records like it) as a whole. Deicide's compositions and performances are solid and serious throughout". He also suggested, "newer death metal fans will do well to start off their collection with Legion".