A music video was produced for the album's single, "We Will Rise," which saw moderate airing on Headbanger's Ball and Uranium. It featured a legion of people racing across a beach under a darkened sky. According to the band, one of the participants in the video hurt an ankle considerably in leaping off a large hill but did not sue.
At its time of release, Anthems of Rebellion gave Century Media its then highest first-week Soundscan sales in the United States, and later became one of the top ten best-selling albums under the record label. 
In numerous regions, a bonus DVD was supplied with the initial release in three forms. Track listings would be identical, save the Europe jewel case edition, which omitted "Exist to Exit" (5.1). The U.S. jewel case release and Europe digipak included all tracks available on the releases.
It is old school and yet modern. It's heavy and everything a good extreme metal album should be. The album features some of their best compositions yet and the arrangements, while simpler in structure than their previous album, are thick and rich and full. It's hard not to like the album if you are into extreme metal not only because it features some excellent songs, but also for the near perfect production and the heavy sound the band has achieved.
Anthems of Rebellion was received mostly well. Sean Palmerston and Laura Taylor of Exclaim! praised the album stating that it is the "finest album so far without a doubt" and that "with Gossow's death-rattle vocals, and tight performances all around, Anthems of Rebellion is a pretty delectable razor to the eardrums", respectively. Gregory Bradley of Metal Review called the album of "a vicious beast of millennium death/thrash." He praised the Angela Gossow vocals stating that they "are absolutely top notch, some of the best and most signature vocals out there." Bradley also comments that the backing vocals were "a very welcome surprise." Justin Donnelly of Blistering that praised Gossow writing that her "vocal delivery is a solid improvement, and not only compliments the aggressive music, but seems to bring more power and style than ever before", commented that the inclusion of Christopher Amott's backing vocal "works surprisingly well." He said that everything on Anthems of Rebellion makes it "one of Arch Enemy's most finest, most diverse yet satisfying releases to date." About the clean vocals, Jackie Smit of Chronicles of Chaos commented that they were "well-implemented." Smit felt that the keyboard lines "add a welcome dash of variety to the proceedings." Nevertheless, he disliked of the lyrics, but stated that "Arch Enemy have produced perhaps their best record to date", though.
EvilG of Metal Rules praised the producer and the band. He said that "the sound and clarity of the album is great, thanks to producer Andy Sneap" and that the band "easily outplays many of their peers from the melodic death metal and blackened thrash metal heap, yet they still manage to push the boundaries of their musical style and create a fury that is second to none." Critic Anders Sandvall, also of Metal Rules, stated that "the band has done a masterpiece in their genre."Carl Begai of Brave Words & Bloody Knuckles called the Sneap's production of "ridiculously perfect" and stated that "Metallica could learn a lot from listening to this album." He comments that Anthems of Rebellion "is an excellent follow-up to their now classic breakthrough album", but the band will probably never surpass the song "Enemy Within" from Wages of Sin. Ralph of Lords of Metal praised the album and the production of Sneap. He completes stating that Anthems of Rebellion is a "very complete metal record." David Atkinson of RevelationZ Magazine praised the album stating that "this is everything Metallica was, should have been and could have been!". Atkinson compared it with Master of Puppets by Metallica and Peace Sells... but Who's Buying? by Megadeth and called it of classic.
Mike Stagno of Sputnikmusic called Gossow's performances of "superb". He also mentioned that the band balances out the heavy and melodic parts very well and praised the album when he wrote that "infectious melodic guitars, top notch vocal efforts, superb song writing, this album has everything one would want from a band of this stature. Definitely an impressive album." However, Stagno wrote that the songs "Tear Down the Walls" and "Anthem" are unnecessary. Tony Daley of Blabbermouth.net said that Mike Amott is a fantastic guitarist, but felt that the album "still isn't quite what he and his band are realistically capable of." Vincent Eldefors of Tartarean Desire praised Gossow, however, he said that the previous release was more impressive. Todd Kristel of Allmusic, who wrote a negative review to the album, stated that "in general, the lyrics aren't particularly impressive and the band has only mixed success at musically evoking the pervasive sense of menace they seem to be going after." Meanwhile, he concluded that it "is a reasonably solid album that should appeal to the band's fans."