With World War II raging across Europe, death and chaos hung in the air. It was a perfect storm of conflict and blood to bring about the Dark Lord Dracula... almost as if it were planned. And it was, by the evil Countess Bartley.
Two heroes, John Morris (wielder of the Vampire Killer) and Eric Lecarde (wielder of the Alucard Spear), each have motivation to rid the world of the darkness cast across it: John wants a piece of Dracula after the vampire killed his father. Meanwhile, Eric is looking for vengeance against Countess Elizabeth Bartley, niece of Dracula and the woman that killed Eric's lady-love, Gwendolyn (once again proving that, in the Castlevania series if you're a woman, you're probably fucked, or evil, or most likely both).
At Dracula's castle, though, they find no evidence of the Dark Lord. Instead, the castle is but the first leg of a journey across the continent, as the Countess Bartley flees to other safe havens to plot world domination (which is a really vagure plot, as far as we're concerned). It's in Castle Prosperina, the last leg of the quest, that the heroes come face to face (and defeat) the Countess. But the quest isn't over just then.
No, Dracula is back, and to rid the world of evil (for a spell, anyway, since that evil never seems to come out no matter how hard you scrub) the Dark Lord must once again be defeated. The two heroes bravely fight against the evil vampire king, valiantly saving the day and curing the countryside of its continuing ills for a time.
Castlevania Bloodlines isn't just a sequel to the Castlevania series, but also a sequel to Bram Stoker's original novel, Dracula. John Morris, hero of the game, is the son of Quincy Morris, one of the side characters in the novel (who is there at the big fight against Dracula at the end of the book).
Meanwhile, much of Eric Lecarde's backstory is covered in Castlevania Judgment. In his youth he was given the Alucard Spear by (of all people) Alucard. Dracula's son forged the spear to aid the Vampire Killer. The two weapons could be used in a battle together to defeat Dracula, which more or less happens (in continuity, anyway -- in the game you play as either hero, not both at once, so in-game it's more of an "instead-of" proposition instead of an "along with" deal). After Eric's era, though, the spear is never really heard from again, so its strength must not have been that great.