A Bullet For My Valentine története 1996-ban kezdődött, amikor Matt és Moose a Trauma nevű együttesben játszott, ám Moose úgy döntött, hogy nem szeretne többet gitározni. Elhagyta az együttest, és Padge segítségével elkezdett dobolni.Később, 1998-ban ismét találkoztak a Bridgend College nevű iskolában, és megalapították az új zenekart, a 12 pints of my girlfriend's blood-ot, majd elég hamar nevet változtattak Jeff Killed John-ra. Az együttes tagjai Matthew "Matt" Tuck (ének, gitár), Michael "Padge" Paget (gitár), Nick Crandle (basszusgitár) és Michael "Moose" Thomas (dobok) voltak.Kezdetben csak Nirvana- és Metallica-feldolgozásokat játszottak, csak később kezdtek el saját dalokat írni. Ezekből a dalokból kisebb átalakításokkal három maradt fenn: a 4 Words (to Choke upon) , a Nation to Nation, melyből később a Turn to Despair lett ; és az Eye Spy, ami a későbbi Hit the Floor elődje.1998-ban készült el az első demó CD-jük, a Better off Alone, majd 2001-ben a Don't Walk Away. Ennél a 2 lemeznél még mindent önerőből, producer nélkül csináltak.2002-ben, a Pynci scheme által szponzorált, két dalt tartalmazó CD jelent meg, a You/Play with me; a producer Greg Haver volt. Ugyanebben az évben, Steve Stranger lett a menedzserük, és körülbelül egy éven át dolgoztak együtt.[1]2003-ban jelent meg az öt dalt tartalmazó Jeff Killed John című EP, és az év vége felé kaptak lehetőséget egy újabb, négy dalt tartalmazó EP elkészítésére, ám Nick távozott az együttesből. Ekkor nem sok kellett ahhoz, hogy végleg feloszlassák az együttest. Ekkor határozták el, hogy az akkor divatos nu-metal stílus helyett saját stílust alakítanak ki. Nick Crandle helyére belépett Jason "Jay" James; aki gyakorlatilag helyet cserélt Nickkel, ő ugyanis Jay előző, NUKE nevű együttesében játszott innetnől fogva. Ekkor nevet változtattak, először Opportunity In Chicago-ra, majd később Bullet For My Valentine-ra.

Matthew Tuck, -Balu-, Artemis1995, kisskrisztina91, jozsikiraly