Группа Walls of Jericho была основана после распада двух детройтских групп. Первая из них называлась Earthmover и в ней на тот момент играли Майк Хасти (гитара) и Уэс Кили (ударные). Вторая — Universal Stomp, её участником был Аарон Руби (бас-гитара). Распад этих групп и побудил трёх друзей создать новую группу. В это время Кэндес Каксалэйн, до этого 2 года певшая в группе Apathemy[1] , пришла на прослушивание в новый коллектив. Так в сентябре 1998 года у новоявленной группы появились вокалистка и фронтмен в одном лице.
Первые несколько месяцев на месте второго гитариста играли знакомые музыкантов, пока они не пригласили на постоянное место своего близкого друга Криса Роусона. Имея в составе пять человек, группа стала завоёвывать хардкор-сцену Детройта. Вскоре, в апреле 1999 года Walls of Jericho выпустили свой первый EP 7" на лейбле Underestimated, после которого вышел EP на компакт-диске. Он содержал материалы предыдущего мини-альбома вместе с новым материалом, и был издан во Флориде лейблом Eulogy Recordings под названием A day and a thousand years. После продолжительного турне в поддержку своего диска, на Walls of Jericho обратили внимание Ferret and Trustkill. Группа подписала контракт с Trustkill и уже в декабре 1999 года на свет вышел первый студийный альбом The bound feed the gagged. Весь следующий год музыканты привели в турне и на фестивалях. После окончания очередного турне, барабанщик Уэс Кили заявил о том, что покидает группу дабы окончить учёбу в Сиэтле. Для группы из Детройта это означало дальнейшую невозможность сотрудничества, поэтому на место Кили был взят бывший барабанщик Suicide Machines Дэрек Грант. Пять месяцев спустя и он заявил о своём уходе из группы.
