Pat Thetic e Justin Sane nel 1988 sono gli unici punk rockers di Glenshaw, Pennsylvania, città nella quale sono cresciuti. Pat riesce con difficoltà a suonare la batteria e Justin non è molto meglio alla chitarra, ma decidono ugualmente di iniziare una band insieme alla sorella di Justin, Lucy Fester, come cantante. Varie persone si succedono per le prime prove al basso e alla seconda chitarra mentre, dopo un periodo passato senza nome, nel 1989 il gruppo viene battezzato Anti-Flag. Il nome è ispirato alla scena punk di Pittsburgh, capitale della Pennsylvania poco distante da Glenshaw, piena di ragazzi che utilizzano lo slogan "libertà, non fascismo". Ma loro stessi hanno un'idea del punk fascista, portano giacchetti con incollata la bandiera americana inneggiando alla fedeltà alla nazione e poi vanno a vedere concerti di band come Exploited e Circle Jerks cantando le loro canzoni, i cui testi sono totalmente in contraddizione con le loro idee.
Ma dopo un solo show in una chiesa, il gruppo si scioglie: Pat e Justin continuano a suonare in altre band fino a quando, nel '92, si recano nella costa ovest statunitense, a San Francisco, per conoscere meglio l'attivissima scena punk locale, dove Pat rimane per poche settimane ma Justin per circa otto mesi. Al ritorno a Pittsburgh (i due si trasferiscono in questa città) decidono, nel febbraio del 1993, di formare un nuovo gruppo, iniziando le ricerche per un bassista, trovato poi in Andy Flag, un ragazzo che Justin aveva conosciuto qualche tempo prima (i due erano gli unici punkers di un gruppo giovanile parrocchiale al quale le loro madri li avevano costretti a partecipare). Iniziano così le prove del nuovo gruppo, e dopo circa due mesi vengono invitati a suonare ad uno show radiofonico dal vivo a Pittsburgh. Ma la nuova band non ha ancora un nome: Pat, che interpreta il ruolo di batterista, e Justin, che suona la chitarra e divide le parti cantate con Andy, pensano così di riutilizzare il nome Anti-Flag, che ritengono ancora di attualità per spiegare lo stato della comunità punk rock. I tre non vogliono che la loro band sia solo un mezzo di intrattenimento, ma vogliono comunicare qualcosa, vogliono costringere la gente a pensare. Sempre nel '93 la band registra un primo demo da 17 canzoni, prima che l'anno successivo escano uno split con i Bad Genes, intitolato "Rock'n With Father Mike" (due brani a band), e l'EP "Kill Kill Kill" (quattro brani), entrambi per Self-Serve Records. La band intanto cerca di suonare ovunque può, anche se non è un'impresa facile in quanto non hanno un pulmino (il che in ogni caso li costringerebbe a non allontanarsi troppo dalla loro zona), non conoscono nessuno al di fuori di Pittsburgh e non hanno molti soldi. Nel '95 la band comunque registra alcuni brani dal vivo che rilascia sottoforma di una musicassetta intitolata "Rotate", contenente 10 brani, mentre sempre lo stesso anno esce anche uno split con i God Squad (due pezzi a gruppo).
Il gruppo continua anche l'attività live, riuscendo ad organizzare, anche grazie a band loro amiche che sono già state in tour, come Bad Genes e Submachine, un primo tour degli Stati Uniti (con qualche tappa in Canada), avvenuto nell'estate del '95, per il quale gli Anti-Flag hanno anche, per la prima volta, un pulmino, che è stato regalato ad Andy da suo nonno. Ma durante questo tour diventa chiaro che Justin e Andy non vanno molto d'accordo quando sono costretti a stare per molto tempo insieme, arrivando alle mani parecchie volte; e la cosa si ripete anche durante il breve secondo tour (dura una decina di giorni) della primavera del '96, portando Andy ad abbandonare gli Anti-Flag subito dopo, sostituito per qualche tempo da Sean dei Bad Genes. Comunque la band nel frattempo ha organizzato per quell'estate un tour con i canadesi DBS, che hanno conosciuto molto tempo prima al Gilman Street, famoso locale della East Bay californiana, e per l'occasione, visto che i due gruppi si stimano molto l'un altro, hanno anche pensato di rilasciare uno split assieme: il management dei DBS è la Nefer Records, con il quale la band ha un contratto, ed è pertanto questa etichetta che nel '96 rilascia l'album, intitolato "North America Sucks", in 1.000 copie. Durante il tour di due mesi con i DBS che si tiene quella stessa estate è un amico di Pat, Justin, che interpreta il ruolo vacante di bassista.
Nel dicembre del '96 esce il primo full-length della band, un insieme di brani nuovi ed altri già inclusi in EP e split precedenti, ma tutti registrati ancora con Andy: l'album, "Die For The Government", esce edito dalla New Red Archives di Nicky Garratt degli U.K. Subs, storica punk band, che li ha conosciuti grazie ad un demo inviatogli da un amico degli Anti-Flag.
Per un concerto che la band tiene a Pittsburgh la vigilia del nuovo anno 1997 Chris Head, un ragazzo che avevano conosciuto poco prima, suona il basso per gli Anti-Flag, ripetendosi anche per il tour di promozione di "Die For The Government" di inizio '97. A Pat e Justin Chris piace, e vogliono che continui a suonare con loro, ma devono trovargli un posto nella line up: Chris, (che gli altri due chiamano affettuosamente "Gimmie") infatti non è un bassista, ma un chitarrista. Per questo non vogliono sacrificarlo al basso, ma non vogliono nemmeno che lasci il gruppo: decidono così di utilizzarlo alla seconda chitarra, iniziando le ricerche per un nuovo bassista, che ancora però non hanno trovato quando manca solo un mese alla partenza per un tour con gli U.K. Subs, il loro reunion tour per festeggiare i 20 anni della loro formazione. E' a questo punto che gli Anti-Flag decidono di concedere il posto vacante a Jamie Cock, una ragazza conosciuta durante la tappa del tour estivo del '95 nella sua città, Toronto, in Canada: con questa nuova formazione, gli Anti-Flag nella primavera del '97 partono così in tour insieme agli U.K. Subs. Qualche settimana dopo la loro partenza esce, grazie alla collaborazione tra Six Week Records e Clearview Records, uno split picture disc live 10" con i Dread (gli Anti-Flag propongono undici brani), seguito poco dopo, sempre lo stesso anno, da uno split con gli Against All Authority intitolato "Reject" (con tre brani a band) ed uno con i giapponesi Obnoxious, "I'd Rather Be In Japan" (due pezzi ciascuno).
Nel frattempo gran parte del catalogo della band è ormai andato esaurito e, desiderosi soprattutto di ri-rilasciare lo split con i DBS (che si è esaurito in poco tempo), la band decide di creare una propria label, la A-F Records. La band tra l'altro non vuole neanche che la Nefer ristampi lo split perché, così come i DBS, non si sono trovati bene con l'etichetta, anche perché si è comportata slealmente nei confronti dei due gruppi, mentendo anche su cose di poco conto, durante il tour con i DBS che era stato organizzato, per la parte canadese, proprio dalla Nefer. Ma la Nefer ha i diritti sui pezzi dei DBS, e pertanto la band rilascia solo i propri brani (dieci) insieme ad altri nove brani inediti, nell'album "Their System Doesn't Work For You", uscito nel gennaio del 1998, quando ormai "Die For The Government" ha passato le 20.000 copie vendute. Ma la A-F Records non è nata comunque solo come un'etichetta fittizia per ristampare i lavori della band, ma anche per aiutare gruppi che gli Anti-Flag ammirano, cercando di aiutarli a diffondere la loro musica e le loro idee.
Per Jamie è però molto scomodo fare sempre avanti e indietro dal Canada a Pittsburgh, e pertanto decide di lasciare il gruppo, venendo rimpiazzata da Chris #2 (chiamato col numero 2 per distinguerlo dall'altro Chris già nella band), un ragazzo che ancora frequenta l'high school, con il quale gli Anti-Flag iniziano nel febbraio del '98 a registrare dei nuovi brani. Ma proprio perché #2 è ancora impegnato con la scuola, per i primi tempi viene sostituito, quando non può, da Paul degli Unseen: ma dall'agosto del '98 Chris si dedica interamente agli Anti-Flag, che pertanto continuano le registrazioni del nuovo album, che si protraggono fino al gennaio del '99. L'album, "A New Kind Of Army", esce nel maggio del '99 dopo vari ritardi (che ne hanno spostato il rilascio di due mesi), edito in cooperazione tra la A-F e la Go Kart Records di New York. La band parte così nuovamente in tour girando Canada e Stati Uniti e partecipando anche al Vans Warped Tour quella stessa estate, mentre in autunno "A New Kind Of Army" esce anche in Europa, dove la band ancora non è mai stata (infatti, nonostante stia in tour ormai dai sei agli otto mesi all'anno, la band non è mai uscita dal continente Nordamericano). Nel 2000 partecipano nuovamente al Warped Tour, mentre poco dopo, sul finire dello stesso anno, firmano con la Fat Wreck Chords, etichetta di Fat Mike dei NOFX ormai diventata insieme alla Epitaph di Brett Gurewitz, ex chitarrista dei Bad Religion, la più importante casa punk mondiale: i quattro non perdono tempo, registrando (per la prima volta insieme ad un produttore) al Sonic Iguana Studios di Lafayette, Indiana, in due sessioni di studio nel novembre del 2000 e nel gennaio e febbraio del 2001, dei brani per un nuovo album, "Underground Network", che esce in aprile. La band dimostra ancora una volta il suo impegno in campo sociale promuovendo, insieme ai Rage Against The Machine, una campagna per liberare Mumia Abu-Jamal, un uomo di colore condannato a morte incriminato, sembra con scarse prove, di avere ucciso un poliziotto.
L'11 settembre del 2001 la band è in studio quando viene a sapere degli attacchi kamikaze al World Trade Center di New York: subito, il giorno dopo, Justin scrive una canzone al riguardo, "911 For Peace", che viene registrata il 13 dello stesso mese. L'ondata di patriottismo che investe gli Stati Uniti (unito a quello già tradizionalmente presente negli Americani) in seguito a questo evento provoca non pochi problemi alla band, a causa del suo nome: già in passato avevano avuto problemi con il nazionalismo di qualcuno, quando ad esempio a Providence nel tour con gli U.K. Subs un gruppo di buttafuori aveva rubato la loro bandiera americana (che la band ammaina sul palco ad ogni concerto) o quando, a Newark, nel Delaware, un gruppo di ragazzi voleva picchiarli a causa sempre del loro gesto fortemente simbolico di ammainare la bandiera (gli Anti-Flag erano stati poi protetti dai loro fans). Le difficoltà di portare un simile nome si notano anche dal fatto che la band per farsi scrivere le lettere dai fans deve invitarli a non scrivere sulla busta "Anti-Flag", dato che spesso lettere con tale intestazione non vengono consegnate.
In occasione della guerra lanciata dagli Stati Uniti all'Afghanistan (al regime talebano, accusato di proteggere Osama Bin Laden, la mente dietro gli attentati), la band organizza facendo ricorso ai propri fondi, a quelli della A-F Records ed anche a quelli personali, un tour chiamato "Mobilize For Peace", nel quale suonano anche gruppi come Against All Authority e Thrice, che parte nel febbraio del 2002, pochi giorni prima che esca, sempre in febbraio, "Mobilize", un nuovo album edito dalla A-F contenente otto inediti (quelli incisi nelle sessioni di studio di fine estate e autunno 2001) ed otto vecchi registrati dal vivo durante due concerti a Pittsburgh. La prima parte del "Mobilize For Peace" dura fino a marzo, mentre dopo un paio di settimane di pausa inizia la seconda parte, alla quale partecipano anche gli Strike Anywhere, che si protrae fino ad aprile: il tour è stato un gran successo, registrando quasi in ogni posto il tutto esaurito, ma il il New York Times, uno dei principali quotidiani nazionali, nomina gli Anti-Flag in un articolo come una di quelle band che nessuno ascolta più in seguito agli attentati.
Sul finire di aprile la band parte per la prima volta per l'Europa, suonando insieme ai Donots di supporto ai Millencolin nel loro tour mondiale di promozione al loro album "Home From Home", mentre in estate partecipano nuovamente al Warped Tour. In settembre esce uno split con i Bouncing Souls, "BYO Split Series Volume IV", come quarta edizione della serie di split della BYO (Better Youth Organization) Records.