Au départ, le groupe avait pour nom Jeff Killed John avec Nik Cradle à la basse, qui reprend des classiques du rock tel que Nirvana mais l'arrivée du bassiste Jason James change l'orientation musicale et le groupe se renomme Opportunity in Chicago pour finalement à nouveau changer de nom et s'appeler Bullet For My Valentine. Leur style de musique est un mélange de Heavy Metal des années 1980-1990, aux sonorités s'apparentant à Pantera ou Metallica, et d'hardcore punk, un tout nouveau style émergeant. En octobre 2004, le groupe signe un contrat chez Sony BMG via le label anglais Visible Noise Records.

Le groupe sort un premier EP intitulé Bullet For My Valentine chez Visible Noise le 15 novembre 2004 en Grande-Bretagne, et le 30 novembre 2004 aux États-Unis chez Truskill Records.

En octobre 2005 sort leur vrai premier album The Poison qui les fait connaître à travers le monde entier, particulièrement grâce à des hits comme Suffocating Under Words Of Sorrow (What Can I Do) dont le clip a été tourné dans les grottes de Postojna en Slovénie, All These Things I Hate (Revolve Around Me) qui les propulse en haut des charts en Grande Bretagne et aux États-Unis. Le nom de l'album leur est venu à l'esprit lorsque qu'ils ont réalisé que leur style se propagerait partout tel un poison auquel il serait difficile d'y remédier. Quelque temps après, au mois de mai-juin 2006, sort leur nouveau single Tears Don't Fall qui, une fois de plus est un véritable carton partout dans le monde. Cet album fut réédité avec quatre titres bonus et cinq vidéos.

Le groupe entamera sa tournée européenne cette année en passant par la capitale française, Paris, pour la première date de cette tournée européenne le 31 octobre à l'Elysée Montmartre (reporté au 12 novembre, Matt étant « malade »). Ce n'est pas leur premier passage dans la capitale puisque Bullet For My Valentine a déjà joué à la Boule Noire le 8 mars 2006. Peu de temps après, le groupe a assuré la première partie des Guns N' Roses pour leur tournée mais également celle de Metallica pour le Europe Escape from the studio tour en Europe ainsi que celle d'Iron Maiden pour leur tournée américaine.

Bullet For My Valentine sortira également leur tout premier DVD intitulé Live At Brixton la veille du concert en France. Ce DVD est comme son nom l'indique le concert filmé à la salle mythique de la Carling Brixton Academy le 28 janvier 2006 avec en plus pleins de bonus comme par exemple toute la vidéographie du groupe, des photos ou encore la Bullet TV"=, une série de mini-films humoristiques, filmés par des membres du groupe.

Le quatriéme album intitulé Scream Aim Fire est sorti le 28 janvier 2008 dans le monde entier et le 29 aux États-Unis. Scream Aim Fire a été produit par Colin Richardson (Machine Head, Funeral For A Friend) qui a aussi produit The Poison, et a été enregistré à Sonic Ranch, près de El Paso, en 2007. D'après le frontman Matt Tuck, les onze chansons sont dans un registre heavy métal très mélodique avec des refrains et des passages chantés accrocheurs et une musique de fond très intense et heavy c'est beaucoup plus rapide que The Poison, et aussi beaucoup plus agressif