Heathen se formó en la zona californiana de la Bay Área en 1984 por el guitarrista de origen ruso Lee Altus y el batería Carl Sacco. Posteriormente se unirían Sam Crees a la voz  y Jim Sanguineti como guitarrista. Sin bajista actuaron por primera vez el 21 de abril de 1985. Poco después  Jim Sanguinetti abandono la banda para formar MORDRED y fue reemplazado por el guitarrista Doug Piercy, procedente de Anvil Chorus.

Sam Kress era muy bueno como letrista pero no tanto como vocalista, fue expulsado a finales de 1985, entrando en su lugar David Godfrey de Blind Illusion. Para completar la formación el bajista Eric Wong entro en la banda a principios de 1986. En la primera semana de febrero de 1986 actuarían por primera vez como formación estable en el Mabuhay Gardens de San Francisco.

En abril de 1986 graban la demo “Pray for death” que les abriría la puerta al contrato discográfico con Combat. La demo contaría con 6 temas: "Pray for Death, Goblin’s Blade, Open The Grave, Heathen, Deaf in The Silence y World’s End". Y con la formación de David Godfrey a la voz, Lee Altus y Doug Piercy a las guitarras, Eric Wong al bajo y Carl Sacco a las baquetas.

Poco después de dicha grabación, a mediados de 1986 Eric Wong seria reemplazado al bajo por Mike Yaz Jastremski de Griffin. Tras este cambio la nueva formación entraría a grabar a principios de 1987 su opera prima. "Breaking The Silence" se grabaría en dos estudios. Las baterías en el Estudio D de Sausalita California y el resto de las partes en los Music Annex en Menlo Park California. Con el productor Ronnie Montrose y el ingeniero Roger Wiersma.

El disco lo editaría Combat / Music for Nations y contendría 8 temas, dos de los cuales Golbins Blade y la versión de los Sweet "Sett Me Free" saldrían en un single de adelanto. La versión también la grabarían en video. Se regrabarian la mayoría de los temas de la demo, y el tema Heathen saldría como bonus de la edición japonesa. Como tema de nueva composición el mejor ejemplo es el tema que abre el disco. Death by Hanging. El disco vendería unas cien mil copias en todo el mundo.

En enero de 1988 antes de que la gira americana comenzara el batería Carl Sacco seria reemplazado por Darren Minter. Y tras dicha gira David Godfrey abandona la banda dejándola sin vocalista. Reclutarían a Paul Ballof de Exodus y graban una demo de dos temas en octubre de 1988,  pero Mike Yaz también abandona la banda y esta desaparece momentáneamente.

La ruptura no dura mucho y la banda retorna con nuevas fuerzas con la entrada de Vern McElroy y después Manny Bravo al bajo y David Wayne a las voces aunque solo fuera por unas semanas, ya que el vocalista Dave Godfrey reclamaría su puesto, ahora con el apellido de su padre biológico como David White.

La banda graba una demo en marzo de 1989 como adelanto de su segundo disco "Fear of The Unknown" que debió editarse en 1990 pero que por problemas económicos nunca vería la luz. Aun así la mayoría de esos temas a excepción de “Nothing You Can See", saldrían editados en su, ahora si, segundo disco "Victims of Deception" junto a los temas de la demo de Ballof “Mercy Is No Virtue” e “Hypnotized” y la versión de “Kill The King” de Rainbow.

En la edición japonesa entraría la versión de Tygers of Pang Tang “Hellbound”. El disco saldría en 1991 por Roadrunner, en él colaboraría el bajista de Blind Illusion  Marc Biedermann, aunque nunca fue miembro oficial, si echó una mano a su antiguo compañero en Blind Illusion David White. 

Para el consiguiente tour reclutaron al guitarrista Randy Laire. En verano de 1991 Heathen viajan por primera vez a Europa  abriendo los shows de sepultura y al volver a USA continuaron con su propio tour por toda la costa oeste, ya a finales de junio de 1991 el recién adquirido guitarrista Randy y su novia Mya morían en un accidente de coche. Jason Viebrooks entro al bajo e Ira Black fue convocado para sustituir a Doug Piercy y a la otra guitarra vacante entro Thaen Rasmussen. se intentó grabar un ep tributo a Randy y al hermano de David White Jeffrey que murió mientras tocaban en Europa de versiones (Queen, Tygers of Pang Tang, Sweet Savage y Thin Lizzy que no se edito. En 1992 la banda tras tantos cambios desapareció.

Doug Piercy, Lee Altus y Darren Minter se fueron a vivir a Alemania. Doug empezó su carrera como corredor de coches, mientras que Lee y Darren entraron en Die Krupps. Dave White formo su propia banda local llamada  Inner Thrashold, Ira Black se fue a Vicious Rumors y Jason Vierbrooks se fue a Grip INC con el batería de Slayer Dave Lombardo.

Heathen se reunirían para actuar el 11 de agosto de 2001 en  Thrash of The Titans con la formación de David White, Lee Altus, Ira Black, Mike ``Yaz`` Jastremski, y Darren Minter.  Para el concierto tributo a Chuck Billy de Testament y poder recaudar fondos para la terapia contra el cáncer que Chuck sufría. En el festival además tocaron, Flotsam & Jetsam, Sadus, Forbidden, Death Angel, Exodus, Ántrax, SOD, Vio-lence y Legacy (Testament)

Poco después les invitan a participar en Wacken, actuando el segundo día el sábado 3 de Agosto de 2002 junto a Nuclear Assault, Exodus, Blitzkrieg o Kreator entre otros, lo que  da fuerzas a la banda para entrar en 2002 al estudio junto a la productor Rob Beaton para regrabar aquel ep de versiones junto a unas demos excluidas de su segundo disco de 1991 victims of deception, para editarlo bajo el nombre de Recovered en marzo de 2004 con Relentless Records que luego distribuiría de forma regional por compañías locales

Mike Yaz por problemas con su corazón decide abandonar la banda para someterse a un tratamiento, entrando en su lugar Jon Torres (Angel Witch, Laaz Rockit, ...) Jon, Lee Altus y Darren Minter tocaron en la formación de Angel Witch que toco en 2003 BYH. El 23 de mayo de 2005 Mike yaz guitarrista moría a la edad de 42 años por infarto de corazón. 

La banda hoy día gira por toda la Bay Area planteándose la edición de un nuevo disco en estudio, aparte de haber reeditado con 4 temas de la 1º demo como bonus su primer disco. Acaban de realizar una mini gira con Nuclear Assault a finales de junio por el Reino Unido para posteriormente tocar por Bélgica, Holanda y Alemania en diferentes fechas a resaltar como cabezas de cartel en dos importantes festivales underground alemanes, el 16 de julio en el Thrash Till Death (3º edición) y el 9 de Julio en Headbangers Open Air ( 8º edición), en donde Terry Lauderdale sustituye en los show de este verano a Ira Black quedando la formación actual: David White (David Godfrey) - Voz, Lee Altus - Guitarra, Jon Torres-Bajo y Darren Minter - Batería

- 2006