Von Kharkov began life as a panther, but he was polymorphed into a full-grown human by a Red Wizard of Thay. He was promptly named and titled by the wizard, then schooled and trained for combat. Because of his feline heritage, he displayed a strong tendency toward violence and treachery.
Eventually the Red Wizard brought Von Kharkov together with a female enemy and allowed them to become lovers. He then dispelled his polymorphing magic, allowing the panther to tear the woman to shreds. Having forgotten his true roots, Von Kharkov was horrified by the transformation. He suspected that the wizard meant to use him for subsequent assassinations, so the man-panther fled Thay and stumbled into a bank of Mists, which transported him to Darkon. There, he learned of Azalin's secret undead police, the Kargat, so he sought out a vampire to induct him into the ranks. When his master was killed twenty years later, he fled into the Mists once more.
This time, the dark powers embraced him and created the domain of Valachan. Von Kharkov quickly adjusted to his new prison. He learned that it was stocked with black leopards and domestic cats to do his bidding. Also, his hands grew fur and retractable claws (which he hides with gloves).
Years later he found a small statuette of a cat in the lower reaches of his keep, which proved to be the Cat of Felkovic. The magical item eventually hunted him, but such was his confidence in his lordly might that he did not fear it, so the cat mauled him badly. To this day, that magical item is the only thing he truly fears.