Nel 1996 esce il primo full-length, Die for the Government che

Nel 1996 esce il primo full-length, Die for the Government che contiene brani vecchi della band o split, tutti registrati con Andy, l’album esce per la New Red Archives di Nicky Garrat degli U.K. Subs , una punk band storica. Per un concerto a Pittsburgh, con la band suona Chris Head al basso; a Pat e Justin, Chris piace molto e lo vogliono nel gruppo, Chris, però, è un chitarrista, e decidono di metterlo alla seconda chitarra, continuando le ricerche per un nuovo bassista, viene trovata Jamie Cook. Con la nuova formazione gli Anti-Flag, nel 1997 , partono in tour insieme agli U.K. Subs, dopo il gruppo registra tre split: uno con i Dread, uno con gli Against All Authority e uno con gli Obnoxious . A questo punto il gruppo crea una propria casa discografica, la A-F Records, che produce anche un altro album, Their System Doesn’t Work for You , oltre agli altri lavori della band. La casa è stata creata anche per aiutare band che gli Anti-Flag ammirano, producendo la loro musica. Jamie a questo punto decide di abbandonare il gruppo perché era difficile per lei andare dal Canada a Pittsbourgh, così viene sostituita da Chris#2 (vero nome Christopher Barker, chiamato così per distinguerlo dall’altro Chris), un ragazzo con il quale il gruppo inizia a registrare nuovi brani, nel 1998 . Le registrazioni escono nel 1999 nell’album A New Kind of Army .