Az ezredfordulón, a középiskolás David Davidson, Phil Dubois-Coyne és Anthony Buda hozta létre a zenekart, akkor még Cryptic Warning néven. A kreatívan First Demo-nak elnevezett első demójuk 2002-ben készült el, melyen található dalokkal nem csak Bostonban, hanem Massachisettsen kívül is felléphettek. Két évet kellet várni a következő demóra, az Internally Revilved-re – a demót található dalok mind felkerültek a 2005-ben kiadott debütáló albumukra, a Santity’s Aberration-ra, de utóbbi hangzása messze elmaradt a tökéletestől, David elmondása szerint ennek az volt az oka, hogy nem egy metalos producerrel rögzítették a lemezt.
A következő évben megváltoztatták a zenekar nevét – Davidson ezt azzal indokolta, hogy fiatalok voltak és sok hibát követtek el a Cryptic Warning-gel, így szükségük volt egy új kezdésre, ezt biztosította a Revocation. Már ezzel a névvel rögzítették a Summon the Spawn című EP-jüket, majd 2008-ban kiadták az Empire of the Obscene című stúdió albumukat. Minden más kiadásukhoz hasonlóan ennek a kiadatását is önerőből, kiadó nélkül finanszírozták, azonban akiadást követően csatlakoztak a Relapse Records-hoz.
Néhány fellépést követően visszatértek a stúdióba és rögzítették az Existence Is Futile című 2009-ben megjelent albumukat – mely olyan sikeres lett, hogy nemcsak az év egyik legjobb metálalbumának titulálták, hanem világszerte ismerté is tette a csapatot. A harmadik albumuk, a Chaos Of Forms 2011-ben jelent meg, mely elődjéhez méltóan kivalló értékeléseket kapott. Rá két évre készült el a Revocation című lemezük – ugyan népszerű lemez lett, közel sem kapott olyan jó kritikákat, mint elődjei. 2012-ben Anthony kilépett, helyére Brett Bamberger került.
2014 áprilisában csatlakoztak a Metal Blade Records-hoz, ennek örömére pedig visszatértek a stúdióba és év végére el is készült Deathless című korongjuk – az ezt követő turnén a Cannibal Corpse-al és az Aeonnal közösen hozzánk is ellátogattak. A következő évben Phil elhagyta a zenekart, helyére Ash Pearson állt. 2015 kiadták debütáló lemezük remastered változatát, hatodik lemezük, a Great Is Our Sin 2016 júlus 22-én fog megjelenni.
