A New Kind of Army

After the band released Die For the Government in 1996, Andy Flag left due to personal issues with Justin and Pat (they would later reconcile). After that, Sean Whelan of Pittsburgh band the Bad Genes filled in on bass. It was during this time that Sean was also playing in another band (57 Defective) with guitarist Chris Head, whom he introduced to the band. He then joined the band in early 1997 to play bass. Later that year, Jamie "Cock" Towns joined as the new bass player, allowing Chris to move to rhythm guitar (which he preferred). They toured throughout the US and into Canada while continuing to write new music. Some of the shows featured previews of the new songs.[2] Justin said that he wrote nearly 30 songs during this period.

In 1998, Towns told the band that she wanted to leave the band. The band, looking for a new player, ran into a fan named Chris Barker who told them he could play. The band let him in, and he took the name Chris #2 (sometimes simply called #2).[3]

By the time Chris #2 had joined, the album had already been mostly written and recorded. The band had spent time recording in various houses in Pittsburgh, including Justin's parents' house. When he joined, the band reconvened at the house so he could record his bass for the songs. Recording was finished in January 1999, while Chris was still in high school. Justin remarked that there was more pressure on writing the songs than on the previous album due to Andy's departure, and him having to write all the lyrics.[4]

Nearly all of the songs were written by Justin alone. As a result, this is the only album that features only him as the primary singer. While primarily a punk record, the album also features elements of Ska, Folk, and Melodic Hardcore. The lyrics cover a wide variety of topics including abortion, corruption, police brutality, racism, fascism, and unity within the American Youth. Tearing Everyone Down and Captain Anarchy continue the themes from Die for the Government of criticizing the "fake jock punks" who were ruining the scene at the time. The band would later point to Tearing Everyone Down as the track that would pave the way for their future songs, including "I'd Tell You But..." and "The Criminals".

During a live show, Chris #2 joked that Justin was the only one who liked playing Captain Anarchy live, as he and Chris Head "hated the song", and Pat "hated playing any Anti-Flag songs". The title track was written by Justin as one of the last songs for the album. He explained that he was having a difficult time coming up with concept for the record, then came up with the song on a walk, returned home, and wrote the song in 30 minutes. The song was inspired by President Clinton ordering the bombing of Iraq in order to distract the nation from the Monica Lewinsky Scandal. That's Youth describes the band's experience growing up in Pittsburgh with their friends. No Apology is a pro-choice anthem and, according to the band, is one of the only songs on the album that they hadn't played live (Although Chris #2 would play an acoustic version of the song in an Instagram live stream[5]).

Got the Numbers is one of the heavier songs on the album, and features pounding drums from Pat and fast paced bass playing by Chris 2. It remains one of the band's more popular songs, even though Chris 2 said Pat didn't like the song either. Even though Justin is the only singer on the track, Chris 2 usually sings the chorus when they perform it live. No Difference is a slower track that describes freedom of being at a punk show with fellow friends. I Don't Believe is similar to songs from Die for the Government in that it questions the wave of nationalism throughout the country as a result of the Gulf War. Right On is credited to the entire band and mocks people who have insulted the band in various cities.

What You Don't Know questions the secret nature politicians engage in that results in US laws and policy, presumably without input from the American people. Free Nation? attacks the Christian Right and the Republican Party for claiming to uphold "christian values" while pursuing policies that attack non-whites. Chris 2 said that he had difficulty recording this song because the band didn't have a click track, so he had to manually count himself in to start the song on time. He later called it one of his favorite Anti-Flag songs. Outbreak references the Lewinsky Scandal and the bombing of Iraq, similarly to the title track and asks "Who is the real terrorist?". An early version of the song appeared on the A-F Records cassette This Is East Coast Punk, and featured a spoken intro by Sane.[6] Police Story describes the Death of Jonny Gammage by the police in 1995, claiming "We've got no rights when cops can kill". The song remains one of the band's most request songs to play live, but Chris 2 said that they don't play it because they never found a way to make it work live.

Consumer Song was one of the last songs included on the album, along with New Kind of Army. It's a mournful, slow song featuring Justin playing guitar by himself, similar to folk-punk artist Billy Bragg. He had written the song at the end of the sessions, and the band were unable to record a full version of it. They decided to include the solo version on the record in order to show off their appreciation of Bragg. The song addresses the flaws of capitalism, and calls for people to watch where they spend their money, as their buying habits "support abuse in the third world scene". This Is Not A Crass Song features 3 minutes of silence at the end of the song before featuring audio of the band jamming in the studio.

The band recorded the album in a similar manner that they did with Die For the Government, renting equipment from local stores to use. Joe West, who had helped produce and engineer the previous album, returned to help them record again. Some of the songs featured guests, including former bass player Jamie "Cock" Towns, Azi Masladahan, Hoss, Mike Poyzle, Reagan Squad, Jim Weber, and Neil Linn.

The album features a drawing by Justin's sister, Lucy, that parodies the famous flag image at Iwo Jima during World War II for the cover. Underneath, the band wrote "Anti-Flag does not mean Anti-American. Anti-Flag means anti-war. Anti-Flag means unity." The booklet also featured a prayer from Mark Twain, and a fold out poster with the phrase "Too smart to fight. Too smart to kill. Join now. A new kind of army."

In the album's liner notes, the lyrics spelt women as "womyn". The band wrote that this was "not a misspelling, but a result of feminist conscious". The band would continue to do this for every album that contained the word.

The album was released jointly on Go-Kart Records and A-F Records. Greg Ross, the label owner, was friends with Pat and offered to sign the band to release the album. They later revealed that the album was originally scheduled for an April release date, but it got pushed back to May because the CD wasn't ready.

The band had wanted to release the album on Fat Wreck Chords, but Fat Mike didn't want to, as he felt the band were too different from the other acts. He offered to release it on Honest Don's Records, the subsidiary for Fat, but the band declined, viewing it as a "second-tier label". When they met on Warped Tour in 2000, Mike told them he was so impressed by them saying no that he offered to sign them to Fat for their next album. They would release their next 2 albums on the label.

In 2004, the band rereleased the album on A-F Records due to the rights reverting back to them. The rerelease included new artwork.

The band later said that this was the first Anti-Flag album to sell more than 100,000 copies.[7]

All songs written by Justin Sane, except where noted.

• Justin Sane – lead vocals, lead guitar
• Chris #2 – backing vocals, bass guitar (Credited as #2)
• Chris Head – backing vocals, rhythm guitar
• Pat Thetic – drums, percussion

Both Police Story and The Consumer Song would later be rerecorded for the band's 20 Years of Hell Series. The Consumer Song received a full band recording for the first time.

Tearing Everyone Down, A New Kind of Army, and Free Nation? would all be featured on the band's album Mobilize as live recordings. In addition, Tearing Everyone Down and Got The Numbers would be featured on the live albums Live Vol 1 and Live Vol 2, respectively.

Justin would later go on to call A New Kind of Army his least favorite Anti-Flag album.[8]