Velma gets a call from Cuthbert Crawley, a lawyer for Velma's family who tells her that she's inherited her great uncle's property and castle in Transylvania. Velma turns the offer down, replying she wants nothing to do with her uncle, puzzling the gang. Mr. Crawley understands, revealing the curse over the estate. He says that if anyone gets too close to the Baron legacy, then what they love the most will be destroyed. As they head outside, Fred hears a noise from the Mystery Machine, then it explodes and a mysterious character with a mask appears. Crawley reveals that it's the ghost of the Baron, Velma's old ancestor. The remains of the machine explode again, with words saying stay away from Transylvania, but Fred declares that is where they're going to find the person responsible for destroying the Mystery Machine, saying this time "it's personal".
Having no other option, the gang ride in the express. Velma reveals the truth that her real last name is Von Dinkenstein, which her great grandparents shortened to Dinkley when they moved in from the old country. Her ancestor is Baron Von Dinkenstein, who was said to have created a monster called Frankencreep (which inspired famous novelist Mary Shelley to write her novel Frankenstein). Velma explains that this was the reason that she started solving mysteries. All of a sudden, the train starts to pick up speed. After getting everyone to the last car, Shaggy goes to the front of the train, but finds not the conductor but the Masked Baron's ghost, who states the curse is now affecting the gang just before he tears off the control panel, throws it and disappears. The gang still manage to save the last car, the people, and themselves just as the train derails and explodes. As they arrive in town, the people in the car are the inspector, burgermeister, and Iago, a hunchbacked servant of Castle Von Dinkenstein. He takes them to the castle, where they meet Mrs. Vanders, the housekeeper. They arrive in the Baron's laboratory and find Frankencreep in solid ice. Velma said she could prove that the monster was a fake and tells everyone else to leave. As the rest of the gang leave, Mrs. Vanders shows Velma a machine which hypnotizes her.
Strange things start happening when the gang goes to a village festival. Daphne is shocked to find her current size clothes are now too tight for her, as she has gained weight. Shaggy and Scooby suddenly become brave and courageous and are not hungry either, and Fred mourns his beloved Mystery Machine. Iago arrives and saves the gang, who are being threatened by the villagers, and he tells the gang Velma has gone insane.
When they return, Velma now has pink hair, new clothes, and has brought Frankencreep back to life. The villagers attempt to defend themselves and take down the monster, but Frankencreep scares them off. Daphne and Fred are still miserable by the losses and wander off to be alone, while Shaggy and Scooby, who are still brave, decide to capture Frankencreep themselves. Velma manages to knock out the monster and decides to remove Shaggy and Scooby's brains to put them in Frankencreep (stating the two of them together have one brain). Fortunately, things start to get better, as Fred finds a workshop and builds a new mystery machine, Daphne finds that her dress is an inflatable suit with air and Frankencreep rips off Shaggy and Scooby's new outfits, turning them back to their old hungry and scared selves. When Frankencreep starts to chase them, it accidentally hits the lever of the machine that hypnotized Velma, bringing her back to normal. Iago appears and tells them that they need to leave the castle because it is about to explode. They manage to escape and fake their deaths.
They lure the burgermeister, inspector, gypsy, and Mrs. Vanders to the express train. They trap them in an express car as the train drives. Just as the mystery seems to be solved, Frankencreep reappears revealing to be a robot with Iago, who then reveals he's actually an undercover DOD agent named Shimidlap. He says that one of the exoskeletons the infantry of humans was stolen from their research labs and traced it to Transylvania. It's soon revealed that instead of a suspect, it was actually a conspiracy of revenge: the burgermeister, inspector, gypsy, and housekeeper were all in on this. The inspector is unmasked to be Cuthbert Crawley who is actually Cuthbert Crawls (the partner of Cosgood Creeps where they haunted a mansion as green ghosts in "A Night of Fright is No Delight" from Scooby-Doo, Where Are You?). The burgermeister is exposed by Velma to be C.L. Magnus (who posed as Redbeard's ghost), and then the gypsy reveals to be Lila (a singer who posed as one of Mamba Wamba's zombies). Finally, Mrs. Vanders is unmasked revealing to be Mama Mione (the cafe owner and criminal gang leader who dressed up as Old Iron Face). She reveals that Iron Face's mask was also the same mask as the baron's ghost had. The four criminals reveal that they planned on getting revenge and once they discover the history of Velma's ancestry, they bought the castle that was sitting on the natural gas which is explosive (unaware that they could have made a huge fortune if they sell the land). They are soon arrested once again and the Mystery Machine is rebuilt and the gang takes off in it heading straight for home.
At the beginning of the end credits, AlexSuperFan2112 points out some of the plot holes of Mystery Inc's mystery. This gets the attention of the DOD who take him away and cut off his computer broadcast.