Charlotte, a young woman, is abducted by Baron Meier Link, a vampire nobleman who is known not to harm humans needlessly. Charlotte's father, Elbourne, hires D, a dhampir, to find her and rescue her, and alternatively, kill her humanely if she's been turned into a vampire. He offers D $500,000 as a down payment, and offers him $10mil if he carries out the job. D has Elbourne double the payment, and agrees to search for Charlotte.
At the same time, Charlotte's older brother hires another group of vampire hunters, the notorious Marcus brothers, composed of the leader Borgoff, a hulking man named Nolt, a blade master named Kyle, a physically disabled psychic named Grove and a woman named Leila who hunts vampires because of a personal grudge rather than for monetary gain. The two parties (D and the Marcus brothers) race inexorably after Meier Link. However, Meier Link hires the mutant Barbarois; a group of lethal mercenary body guards. They consist of Caroline, a shape shifter; Benge, a shadow manipulator; and Machira, a werewolf.
Throughout the course of the film, two of the Marcus brothers, Nolt and Kyle, end up being killed by the mutant Barbarois, while Leila and Borgoff continue their search for Charlotte.
As the story progresses, Meier Link's abduction of Charlotte turns out to not be as it seemed, as it's revealed that Charlotte willingly ran away with Meier Link as his lover. Charlotte rightfully feared that no one would understand their relationship, with her a human and Link a vampire.
Throughout their search, and after both characters save each other from seeming death at separate points, D has a conversation with Leila, where she reveals that she hunts vampires because a vampire killed her mother. D tells her that he hunts vampires as he has no other choice as a dhampir, and she can have a life that someone like him could never have; the life of a normal human. Leila, having not exactly taken the life of a normal human, instead being a monster hunter, fears that no one will mourn her death when that time comes. She make a pact with D, that if either one of them survives, the survivor will bring flowers to the other's grave. D admits that he does not expect himself to survive the bounty hunt, after coming so close to death.
In the final act of the film, Meier Link transports Charlotte in his carriage to the Castle of Chaythe, where Countess Carmilla, Meier Link's matron, waits for them. Carmilla, a ghost of a vampire who died long ago, reigned supreme within the Castle of Chaythe when vampires were all-powerful and unchallenged. However, her bloodlust was so strong that D's father, an ancient, noble vampire king, killed her in disgust. Carmilla promises Meier Link and Charlotte travel to a far away city known as the City of The Night, where they can be free to love each other, which they will travel to in a large and ancient spaceship-like structure hidden beneath the Castle of Chaythe. Carmilla explains that most ancient castles had similar ships hidden within them, and that back when vampires reigned supreme, these ships weren't an uncommon means for vampires to travel to far regions. Carmilla notes that the ship is old and hasn't flown in a long time, and that she doesn't know if the ship will fly safely, but that Meier Link and Charlotte are allowed to take that risk, if they so wish.
D and the remaining Marcus brothers separately trail Meier Link to the Castle of Chaythe, and as they enter the castle in their search for Charlotte, Carmilla plays psychological tricks on them. Borgoff, for example, is shown Nolt and Kyle, the dead members of the Marcus brothers, returning to life. Borgoff ends up also being killed in his surprised and ecstatic state by Carmilla's ghost, and it turns out Nolt and Kyle never returned to life at all. This leaves Leila as the only surviving member of the Marcus brothers as she continues her search for Charlotte inside the castle.
Carmilla manipulates D's mind, and shows him a vision of his mother, in which she apologizes to D for birthing him as a dhampir, and states that she couldn't help it as she was a human in love with D's vampire father, and attempts to explain that humans are capable of loving vampires. D strikes this vision of his mother down with his sword and returns to a normal state.
In a plot twist, Carmilla turns on Meier Link and Charlotte, as Carmilla had actually plotted to kill Charlotte all along, with the reasoning being that Carmilla needed the blood of a virgin to leave her ghostly, ethereal form and return to life. D destroys Carmilla's ghost just as Carmilla is performing the ritual and draining Charlotte of her blood. D, still with a job to do in bringing Charlotte safely back home, engages Meier Link in battle, as Meier Link doesn't want D to take his lover away from him. D stabs Meier Link through the chest with his sword, but not through his heart, injuring Meier Link but allowing him to live. During their encounter, Charlotte has passed away due to the ritual that Carmilla had been performing previously, and D takes the ring off of her finger as proof of her death to bring back to Elbourne, as he ceases battle with Meier Link.
D, along with Leila, make their leave of the Castle of Chaythe, and allow Meier Link to leave for the City of the Night in the Castle of Chaythe's ship with Charlotte's corpse on board. D and Leila agree to ride back into town together on D's horse, as Leila jokingly tells D that the reward is rightfully hers, but this time, she'll allow him to have it. Before riding off, they watch in the distance as the ship hidden underneath the castle takes off to the skies with Charlotte's corpse and Meier Link inside.
In the final scene of the movie, D arrives at Leila's funeral, watching her loved ones mourn from a distance. Many decades have passed since all of the previous events, as a little girl revealed to be Leila's granddaughter approaches and greets D, and invites him to stay with her family for a while. D declines, saying that he simply came to "repay a favor to an old friend, who feared no one would mourn her death." D admits that he was glad she was wrong. The girl thanks him, and D replies by smiling gently at her, and leaves.
Who hires the notorious Marcus brothers?
Charlotte's older brother