Symphony X's 1998 album Twilight in Olympus was released without a title track; instead, the unfinished compositions from those sessions were later re-worked and distributed in fragments throughout V, particularly on the final track, "Rediscovery (Part II) - The New Mythology". Guitarist Michael Romeo has since confirmed this: "About half of ['Rediscovery (Part II)'] is the song 'Twilight in Olympus', maybe a little more".
There are several notable similarities between V: The New Mythology Suite and V, an album by progressive rock band Spock's Beard. Both albums feature cover art bearing a near-identical desert background image; they were released within months of each other in 2000; they are both bands' fifth studio releases; they were released through the Inside Out label; and they are nearly equal in duration, differing only by eighteen seconds.
Robert Taylor at AllMusic gave V: The New Mythology Suite three stars out of five, saying that "As a whole, V: The New Mythology Suite works and proves that Symphony X has chosen to expand, rather than repeat, history in a genre that appeared to have peaked both creatively and technically." Particular attention was drawn to Michael Romeo's guitar playing style, with Taylor likening it to that of Yngwie Malmsteen, but remarking that it "has proved to be both a blessing and a curse for this gifted guitarist. His chops are certainly comparable, but his sound and style are often identical to his idol." He also criticized some of the music and themes as being "all too familiar", as well as singer Russell Allen's "macho vocal style."