FrogReaver
The most respectful and polite poster ever
One possibility is to have the PCs hear about the assassin, perhaps because he/she/it takes out someone unrelated to them - a minor princeling, a high priest, a rich merchant. Or maybe the assassin is so infamous, every unsolved murder is inevitably blamed on him. "Hmm. This was a professional kill. Look's like (fill in the blank's) work."
Or perhaps the PCs are hired to investigate a murder by that assassin.
Another option, one of their contacts warns them that someone has put a contract out of them. If the PCs have any sense at all, they'll start to ask around about the type of folks who would take such a contract.
I like this. PC's are hired to investigate the murder of a prominent figure. As they get closer to figuring out who put the hit on that person that's when a message appears to them to cease what they are doing or else. When they continue the assassin waits patiently for a good opportunity and strikes.
Personally I'd have it be a decently leveled wizard that hired the assassin. Maybe they are good friends and work together a lot now. Either way the wizards magic + the assassins abilities would make for a fun and interesting campaign and gives lots of options leading up toward the defeat of those foes and their plot.
Maybe the would be assassin is a student of the better one that is the wizards friend. There's lots of fun twists and turns that this kind of adventure could have.