‎L’histoire de Melty Blood suit un an après Tsukihime et quelques jours après celle de Kagetsu Tohya. Au début du mois d’août 2001, Shiki Tohno entend parler d’une nouvelle série de meurtres dans la ville de Misaki, similaires à ceux qui ont eu lieu à Tsukihime, dans les dernières semaines d’octobre 1999.
Alors qu’il est à la recherche du meurtrier, il rencontre Sion Eltnam Atlasia qui entame un combat avec lui, tentant de le capturer. Après le combat, elle révèle que sa raison d’essayer de le capturer est d’entrer en contact avec le « Vrai Ancêtre » (en référence à Arcueid) afin qu’elle puisse acquérir des informations sur le « remède contre le vampirisme ». Shiki décide alors de l’aider dans cette tâche. L’histoire se déroule à travers une série de combats. Selon l’issue du combat, l’histoire se ramifiera de deux manières.