2000: Una speranza.

Ancora in tour, stavolta facendo da spalla ai Blink 182. Molti fan sono scioccati da questa notizia essendo i Blink 182 diventati i massimi esponenti della nuova corrente "pop-punk" che sta spopolando nel mondo dei ragazzini come una moda. I Bad Religion però si giustificano dicendo che in questo modo possono raggiungere nuove fasce d'età, la cosiddetta generazione di MTV, dato che ormai i loro video sono una rarità per il circuito televisivo.
A Brian Baker viene offerto un lavoro in un'altra band: i Guns 'N' Roses che Axl Roses vuole far rinascere. Ovviamente declina l'offerta dichiarando che rimarrebbe nei Bad Religion anche senza essere pagato.

Verso la fine dell'anno Greg Graffin si mette al lavoro per scrivere l'ultimo album che manca a completare il contratto con l'Atlantic. Per via dei giudizi ricevuti dal precedente lavoro, questa volta si affida completamente al suo estro. Esce The New America. La formazione è composta da Greg Graffin (voce), Brian Baker (chitarra), Greg Hetson (chitarra), Jay Bentley (basso), Bobby Schayer (batteria). L'album è prodotto da Todd Rundgren, uno degli idoli giovanili di Greg Graffin. La novità è rappresentata dal riavvicinamento di Brett Gurewitz alla band. Infatti scrive, insieme a Greg Graffin, e suona una canzone: Believe It. Da ricordare sono anche New America, usata dal telefilm Beverly Hills 90210 in apertura di una puntata (!), A Streetkid Named Desire quasi un'autobiografia di Greg Graffin, 1000 Memories e Whisper In Time, decisamente ballate rock e Don't Sell Me Short. Come da abitudine alcune canzoni sono disponibili solo in determinate edizioni: The Fast Life, notevole, in tutte le edizioni tranne quella americana, Lose As Directed e Pretenders presenti sul singolo New America e The Queen Of The 21st Century solo nella versione tedesca e giapponese. L'album sembra meglio del precedente, ma comunque permane la sensazione della mancanza di qualcosa, pare che il gruppo sia destinato a sbiadire e finire nel limbo senza più nessun sussulto. Unico video: New America.
Parte l'ennesimo tour naturalmente senza Brett Gurewitz.
Esce un nuovo album dei Vandals, Look What I Almost Stepped In con ancora la partecipazione di Brooks Wackerman. Anche gli Infectious Grooves dopo anni di silenzio escono con un altro album sempre con Brooks Wackerman alle pelli.

2001: Il grande ritorno.

A inizio anno circola un'insistente voce sul ritorno di Brett Gurewitz nella band.
Appena prima della partenza delle date europee a giugno, i Bad Religion si vedono costretti ad annullarle tutte. Durante le precedenti date in Sud America si manifesta sempre più grave il dolore alle spalle e alle articolazioni di Bobby Schayer. Impossibilitato ad alzare il braccio al di sopra della spalla, a causa di una tendinite, seguendo il consiglio dei medici smette definitivamente di suonare la batteria. Per i Bad Religion è una grandissima perdita, Greg Graffin sentenzia: "Il punk ha perso uno dei suoi migliori batteristi".
A questa triste notizia si va a contrapporre l'annuncio ufficiale del ritorno di Brett Gurewitz nella band. Dopo aver detto "definitivamente" addio alle droghe, essersi ripulito e aver organizzato meglio il lavoro nella sua etichetta, Brett Gurewitz sente la necessità di ritornare nella creatura che aveva aiutato a creare quasi 20 anni prima e abbandonato in malo modo. Più o meno sanati i dissidi con i vecchi membri e avendo assicurato Brian Baker di rimanere a far parte dell'organico, il gruppo si ritrova così ad avere tre chitarre! La cosa, mai avvenuta in un gruppo punk, viene spiegata dallo stesso Brett Gurewitz asserendo che a causa dei suoi impegni lavorativi non potrebbe seguire costantemente la band in tour. A questo punto la storica coppia di compositori, quella che ha scritto alcuni pezzi entrati nella leggenda dell'hardcore melodico, è di nuovo unita. Inizia l'attesa per un nuovo album. Prima però c'è da sistemare ancora un paio di cose. La prima riguarda la casa discografica. Il contratto di quattro album con la Sony è finito e i Bad Religion sono "liberi" di scegliere la propria strada. Ma il nome Bad Religion è, è stato e sarà sempre indivisibile da Epitaph, quindi il gruppo ritorna alla etichetta che era stata creata da e per loro. Questa scelta accresce sempre di più l'attesa per un album che tutto fa pensare storico. Manca solo il nuovo batterista, sebbene le tracce sono già quasi del tutto complete. Viene chiesto a Brooks Wackerman di entrare nella band essendo in contatto, tramite i Vandals, con Brett Gurewitz. Entrato a far parte del gruppo, e avendo la metà degli anni di tutti gli altri, la formazione è di nuovo completa.
Brett Gurewitz pone fine al suo precedente gruppo: i Daredevils.
Viene annunciata l'uscita del nuovo album per la fine dell'anno. L'attesa diventa incredibile, destinata a crescere ancora di più quando la data di uscita viene spostata all'inizio dell'anno successivo. A novembre circola già una recensione dell'album e KROQ, la stazione radio da cui è partita l'avventura dei Bad Religion, mette in programmazione il primo singolo tratto dal nuovo album: Sorrow. La canzone, la prima scritta da Brett Gurewitz dall'abbandono, diventa subito una hit seppure non allineata ai classici canoni Bad Religion. La sua fortuna deriva dal riuscire a fotografare le intense emozioni in un'America ancora ferita dall'attentato alle Torri Gemelle. E' giusto sottolineare come la canzone sia stata scritta svariati mesi prima dell'attentato, e questo erge i Bad Religion ad attenti e perspicaci osservatori della realtà contemporanea, portando le loro liriche ad adattarsi a molte situazioni di malessere sociale. L'attesa da parte dei fan è spasmodica, ma a fine novembre qualcuno riesce a ottenere una copia del nuovo lavoro e la mette in Internet. L'album è reso disponibile quasi tre mesi prima della uscita ufficiale.
A dicembre i Bad Religion suonano al KROQ Almost Acoustic Christmas. Questo segna il primo ritorno sul palco di Brett Gurewitz per un concerto live. Viene suonata anche un'altra canzone del nuovo disco: Can't Stop It.