Tyson Ritter en Nick Wheeler richtten een band op in 1996. Dat gebeurde door het samenvoegen van de bands Drowning Fish en Curbside Service. Toen Ritter en Wheeler elkaar ontmoet hadden op een feest vertelde Wheeler aan Ritter dat zijn band nog een basgitarist nodig had. Ritter zei dat hij de juiste man voor hen was. Hij kon op dat moment nog geen basgitaar bespelen. Hij kocht zo snel mogelijk een basgitaar en bleef de hele kerstvakantie in huis om er op te oefenen. Toen hij het al voldoende beheerste ging hij terug naar Wheeler en de All-American Rejects waren geboren. De groep bestond toen niet alleen uit Ritter en Wheeler maar ook uit Jesse Tabish. Nadat Tabish in 2000 de groep verliet bestond de groep nog maar uit twee personen. Ritter werd de zanger van de groep en Wheeler werd gitarist in plaats van drummer. In 2000 brachten ze hun eerste album uit. In 2001 ging de band toeren en daarna werden ze vastgelegd door Doghouse Records. In 2002 werden Mike Kennerty en Chris Gaylor aan de band toegevoegd.
"Gives You Hell", uitgebracht in eind 2008, werd hun grootste hit tot op heden. De piek was een nummer 4-notering in de Verenigde Staten.