Settra the imperishable who was first king of Khemri, starts near the savage orcs, right side of the desert. Arkhan the Black who was Nagash right hand man, starts in Araby, left side of the desert near the questing knights. Khalida who absolutely hates vampires, she starts near spire of sotek dwarfs bottom left. And Khatep who is an exciled mortuary priest and he starts in between mazdamundi and morathi. Hope that helps.