Le jeu débute dans un bar de New Marais, ville fictive ayant pris pour inspiration La Nouvelle-Orléans. Du haut de son statut de baratineur, Zeke Dunbar engage la conversation avec une jolie étrangère. Il lui raconte alors une histoire de son ami d'enfance Cole MacGrath, surnommé le démon d'Empire City.
Lors de la Pyre Night, fête annuelle de la ville célébrant la mort de Bloody Mary, Cole partait sauver des gens coincés dans les catacombes de l'église de New Marais lorsqu'il s'est fait attraper par des vampires connaissant ses aptitudes. Ils lui coupent une veine et font couler le sang sur un cadavre calciné qui n'est autre que Bloody Mary. Après être revenue à la vie, cette dernière mord le cou de Cole pour s'abreuver de son sang puis le transforme en vampire en guise de remerciement mais également d'asservissement. Cole n'a alors qu'une solution pour interrompre cette malédiction : tuer Bloody Mary avant le lever du soleil...