Mappa di Nehekhara.
La Terra dei Morti giace oltre le Malelande. Questo regno desertico è la culla del primo impero dell'umanità: una civiltà conosciuta con il nome di Nehekhara, che si estendeva dalle rive del Fiume Vitae alle coste del Mare Amaro, passando attraverso le montagne.
A est, era dominata dalle città di Lamhia, Mahrak e Lybaras, governate dalle grandi matriarche. Ma Khemri rimaneva il suo gioiello. Quando Nagash l'Arcinecromante, venne sconfitto dall'Esercito dei Sette Re, la Somma Regina Neferata di Lamhia agì rapidamente, proprio quando l'alleanza si stava sciogliendo: rubò in segreto il sapere proibito di Nagash per ricercare l'elisir della vita. Ma il decotto di Neferata era imperfetto e il prezzo per una vita eterna fu un'insaziabile sete di sangue. Neferata aveva involontariamente creato una razza che sarebbe stata la piaga del mondo per sempre: era diventata il primo Vampiro.
Quando sua cugina, Khalida di Lybaras, andò a visitarla per un banchetto, la corte di Lamhia era quasi interamente infettata dal vampirismo. Per dimostrare i suoi nuovi poteri, Neferata sfidò la cugina a un combattimento rituale di fronte agli altri ospiti. Le due donne combatterono di fronte alla nobiltà intimidita, con le lame che riproducevano una danza delicata e letale. Tuttavia, Neferata non era più una mortale ed ebbe la meglio sulla cugina. E mentre Khalida giaceva morente, Neferata lasciò che il suo sangue maledetto infettasse la regina di Lybaras, come atto finale di rancore. La Regina-guerriera si rivolse agli dei, disperata, e ricevette la risposta della Dea-Aspide, che rimosse l'infezione dalle sue vene, in cambio della sua vita. Il corpo di Khalida venne riportato a Lybaras, dove venne imbalsamato e collocato sul trono, pronto per difendere la città come divinità che risiedeva nel mondo dei morti.
Quando i Re dei Sepolcri vennero risvegliati dal loro sonno eterno, Khalida rimase sul suo trono, senza interessarsi alle lotte di potere dei tiranni nonmorti. Tuttavia, quando Lybaras viene minacciata, Khalida agisce, e rapidamente. Quando Asaph glielo comanda, si erge dal trono e comanda le sue legioni in battaglia. Khalida non combatte solo come segno di lealtà nei confronti della dea che l'ha salvata, ma anche per il disprezzo profondo ed eterno nei confronti di sua cugina e di tutti i Vampiri che osano incrociare la sua strada.