Команда была основана в 1981 году вокалистом Полом Балоффом, гитаристами Гэри Холтом и Кирком Хамметом, басистом Джефом Эндрюсом, и барабанщиком Томом Хантингом. Большое влияние на творчество «Exodus» оказали «Motorhead» и такие группы новой волны британского тяжелого металла как «Iron maiden» и «Raven». В 1982 году коллектив записал демки «Whipping Queen» и «Death and Domination», ставшие дико популярными в кругах музыкального андеграунда западного побережья США, и благодаря им считался лучшей трэшевой командой в окрестностях. Однако год спустя «Exodus» потеряли статус лидеров после ухода Кирка Хаммета в «Металлику». Парни не стали особо отчаиваться и быстренько подобрали ему замену в лице гитариста Рика Ханолта, а заодно сменили и басиста Эндрюса на Роба Маккиллопа.

Затем группа заключила контракт с «Torrid Records» и в 1984 году записала на этом лейбле свой дебютный альбом «Bonded By Blood». Однако из-за всяческих неурядиц диск появился на прилавках лишь в 1985 году благодаря стараниям «Combat Records».

Эти проблемы привели к уходу вокалиста Балоффа, которого сменил бывший участник «Testament» Стив Соуза. При его участии в 1987 году был записан не очень удачный альбом «Pleasures of the Flesh». «Exodus» постоянно гастролировали и этим зарабатывали себе очки. Команда сплотилась и в 1989-м записала свой пожалуй самый лучший альбом «Fabulous Disaster». В это время группа находилась на пике славы. Коллектив отправился в успешное мировое турне, окончание которого правда было омрачено уходом ударника Хантинга, у которого открылись проблемы с сердцем. Парни опять же не стали сильно отчаиваться, а заключили контракт с «Capitol Records».

Затем «Exodus» закрылись в студии, предварительно посадив за ударную установку бывшего участника «Anthrax» Джона Темпеста, и начали писать треки для «Impact Is Imminent». Но отсутствие компетентного продюсера и наспех собранная подборка композиций привели к провалу альбома, сведя на нет предыдущие достижения группы.

Из «Exodus» ушел басист Маккиллоп, а вместо него появился Майк Батлер. Несмотря на неплохое качество нового альбома «Force of Habit» в 1993 году группа была распущена (сказались проблемы с руководством звукозаписывающей фирмы, организационные трудности и разногласия между самими участниками), и все музыканты занялись каждый своим делом. В 1997 году, спустя тринадцать лет со времен «Bonded By Blood» оригинальный состав «Exodus» во главе с Полом Балоффом собрался вновь и дал серию концертов. В этот период был издан «лайв» «Another Lesson in Violence». Спродюсированный Энди Снипом диск стал как бы завещанием к музыкальному наследству группы.

Альбом включал все лучшие композиции дебюта и других альбомов, а также ранние вещи с Хамметтом. В последующие годы группа изредка появлялась на сцене, пока не случилась трагедия. 2 февраля 2002 года внезапно скончался Пол Баллофф.