Prior to 1450 AD
Events as Hinted in Other Games
Prior to the events of Castlevania Legends, Matthias ran around Romania (and, really, most of eastern Europe) doing very evil things... the details of which aren't well known and are mostly open to speculation. It is presumed that Castlevania: The Arcade (a Japan-only arcade game released in 2009) takes place during some of these events, but as that game hasn't gotten any kind of translation, nor left it's homeland, we'll just have to ignore that for now.
What is known is that, at some point (after he took the mantle of "Vlad Dracula", although historically this is sketchy at best) Dracula met a woman whom he fell in love with, Lisa. She was a healer in a local town, and the two struck up a romance. Lisa reminded Matthias of his first wife, and he thought she might actually be his first love reborn.
Dracula and Lisa had a child, Adrian Fahrenheit Tepes (a name we feel falls somewhere between "ridiculous" and "fucking stupid" -- thankfully he chose to call himself Alucard), and, probably, there was a time where the three of them were happy together. Certainly (as hinted in Symphony of the Night) Alucard loved his mother, so there had to be some period of happiness in there.
Whatever happened specifically, eventually the villagers of the town decided to burn Lisa at the stake for being a witch -- her healing powers being too "witchy" for the inbred yokels (probably the fact that she was married to a vampire, one called the "Prince of Darkness", didn't help). This, of course, made Dracula very angry. He went even more evil than before, and elected to wage war on all of humanity. Alucard, upon seeing his father's fury (which really, since he was the son of an evil vampire, he should have been prepared for), elects to fight against his father instead of with him.
Needless to say, there have been better father-son relationships in literature and the arts. It makes the relationship between Luke Skywalker and Darth Vader seem positively amicable.
As Castlevania Legends picks up, it had almost 400 years since Leon Belmont defeated Walter and established the Belmont clan as the go-to heroes for vampire slaying. The vampire Dracula had risen to power (potentially now Matthias in disguise), and while known as an evil tyrant in life, he became only worse as one of the undead (and maybe another person).
Thankfully, a girl named Sonia, one of the Belmont clan and wielder of the clan's magic whip, the Vampire Killer, stepped forward to do her best against Dracula and his newly raised army of the undead.
But Sonia was not entirely alone in her quest. At the castle she encountered Alucard, a man she knew from before her quest to destroy Dracula (Alucard, the sly dog, did love the ladies). When the two met in the castle, Alucard elected to test Sonia to make sure she had the power to defeat Dracula. When she showed that her power was greater than even Alucard's, he let the girl through to Dracula.
Dracula, of course, was soon defeated by our heroine, but the townspeople weren't so pleased. While the town was temporarily safe from vampires, Sonia had proved too powerful. Fearing her, the townspeople exiled the Belmonts from the land (this included the child Sonia became pregnant with at the end of the game). But Sonia did vow that so long as evil is in the land, the Belmonts would stand against it (which, you know, Leon had already said, so it was really more of a reaffirmation).
Firstly, this game is no longer in formal Castlevania continuity. It is, officially, the only game to have absolutely no place in continuity. This is, probably, due to the major plot errors this game has when you take Lament of Innocence into account.
As mentioned in the Lament of Innocence article, it is implied that the vampire Matthias from that game eventually becomes the Dracula we all know from the series. Legends, though, posits the vampire as recently turned (with just enough time afterward to sire a half-vampire son). Clearly, without some liberal interpretations of history and the greater Castlevania story, Dracula couldn't both be a 300 year old vampire and a just turned vampire (let alone also a human waging war against the Turks, as actually history so rudely dictates).
(We at the Inverted Dungeon could, of course, come up with an interpretation that could work, but we're saving it for our fanfics.)
Taking into account the fact that Dracula would have had to be born (1431 AD, to be exact), get old enough that Matthias could then steal his identity convincingly, marry a woman, and have a kid, doing all that before 1450 AD stretches all credulity.
With this game removed from continuity, Sonia is no longer the originator of the clan (the implication from the end of this game). The game ends with Sonia having a child, which fans are left to assume is Trevor Belmont (the hero of the next game, chronologically, in the series) -- without Sonia, Trevor's mother was just some unnamed woman. Additionally, this game's removal also means there's no confusion as to if Alucard is also Trevor's father (again, the implied relationship between Alucard and Sonia made this fact ambiguous).
Now, of course, with this game's removal, Trevor is just another Belmont with absolutely nothing special about him (except for, you know, that pesky whip and a penchant for leather kilts).