A Walls of Jericho Detroitban alakult 1998-ban. 2 detroiti bandából alakultak meg: Earthmover volt ez egyik Mike Hasty és Wes Keely-val valamint a Universal Stomp a másik Aaron Ruby-val. Nemsokára a srácok megismerkedtek Candace Kucsulain énekesnõvel is aki az Apathemy tagja volt ekkor. Chris Rawson belépésével lett teljes a banda elsõ felállása. Ekkor még csak haveri körökben zenélgettek kis helyeken. Underestimated címmel jött az elsö EP majd a A Day and a Thousand Years az Eulogy Recordings kiadásában. Utóbbi a Trustkill figyelmét is felkeltette és szerzõdtette a bandát ahol a The Bound Feed the Gagged debütalbum 1999 decemberében látott napvilágot. Turnézás következett az államokban az Earth Crisis,In Flames és Skinlab társaságában. Közben egy tagcsere Derek Grant lett az új dobosuk. 2001-ben pedig ideiglenesen fel is oszlanak. 2 év múlva azonban visszatérnek Alexei Rodriguez dobossal és fellépnek a Hellfesten is többek között. Az új lemez sem várat magára sokáig All Hail the Dead címmel jön ki 2004-ben. Ezt újabb turné követi a Madball, Hatebreed és Sick of it All zenekarokkal lépnek fel. Dustin Schoenhofer személyében újabb dobos érkezik a zenekarba, Alexei Rodriguez sajnos elhagyja a bandát. 2006-ban Ben Schigel producerrel felveszik a With Devils Amongst Us All címû harmadik lemezüket, melyrõl a A Trigger Full Of Promises klippje sokat szerepel a metal mûsorokban. Fellépnek a Ozzfest 2006 turnén is. Az új lemezbõl 2,800 példány fogy el az elsõ héten, ez lesz a legsikeresebb lemezük ezzel. Sick Of It All, Madball, Terror, Comeback Kid zenekarokkal újabb turné európában (Persistence 2006) a 11 helyszínbõl 8 teltházas buli. 2007 újabb európai koncerteket hoz : fellépnek a Hellfest,Pressure Fest,With Full Force Festival,Summer Blast Festivalokon.Corey Taylor segítségével készítenek egy akusztikus kislemezt (Redemption) 2008-ban, majd turné a DevilDriver, Napalm Death, Invitro és 36 Crazyfists társaságában.