Группа Phobia была сформирована в 1990 году в штате Калифорния, США. Основателями принято считать четырех музыкантов: Shane McLachlan, Bruce Reeves, Zach Southall и Marco Soriano. Буквально сразу же после сбора они записывают первое демо "What Went Wrong?". Скопировано с Dark-World.ru.

Затем последовал мини-альбом под названием "All That Remains", выпущенный на лейбле Relapse Records. В 1994 году снова выходит мини-альбом - "Return to Desolation", и группа отправляется в небольшой тур по западному побережью с малоизвестными хардкор и панк-группами. Спустя три года, в 1997, на лейбле Slap-a-Ham Records был издан еще один мини-альбом группы под названием "Enslaved". После Phobia снова отправляются в небольшой тур по всё тому же западному побережью.

Первая полноформатная работа группы была записана в 1998 году на том же лейбле и получила название "Means of Existence". После выхода альбома команда уезжает в тур, но теперь уже по всей Америке. В 1999 Phobia записывают сплит вместе с японцами Corrupted под названием "Destroying the Masses". Также этот год принес группе первый тур по Европе, длившийся 2 месяца и охвативший такие страны, как Бельгия, Германия, Австрия, Шотландия и Нидерланды. В 2001 году музыканты едут в тур по Мексике вместе с командой Anarchus.

После возвращения из Мексики группа издает очередной мини-альбом "Serenity Through Pain". Затем Phobia едут в тур по Америке под названием "Grind Your Fucking Head" вместе с группой Circle of Dead Children. Сентябрь 2001 ознаменовался туром по западному побережью с мелодик-дэт-метал-командой Darkest Hour.

В 2002 году Phobia едут в тур в поддержку альбома "Serenity Through Pain", а также переиздают "Return to Desolation". После они отправляются в тур вместе с Pungent Stench. В мае 2003 проходит еще один тур по Европе, после которого группа издает концертный альбом "Grind Your Fucking Head", в который вошли выступления с этого тура.

2005 год ознаменовался уходом одного из основателей группы, Bruce Reeves (бас), на место которого пришел Leon Delmuerte. Через год команда издает альбом "Cruel", который спродюссировал Scott Hull из Pig Destroyer. Альбом "22 Random Acts of Violence" был издан 22 октября 2006, после чего группу покинул Leon del Muerte, ради своего другого проекта.

Последним на данный момент релизом является сплит с ирландцами Abaddon Incarnate, вышедший в 2011 году.