Loin sous la capitale en ruines de Lordaeron, les cryptes royales ont été transformées en bastion du mal et de la non-vie. Le Prince Arthas avait à la base prévu que Fossoyeuse serait le siège du pouvoir du Fléau, mais la cité fut abandonné lorsqu'Arthas a été rapellé auprès du Roi Liche à Northrend. En l'absence d'Arthas, la Dame Noire, Sylvannas Windrunner, a mené les Réprouvés rebelles à Fossoyeuse, et en a fait son domaine. Depuis qu'ils s'y sont installé, les Réprouvés ont travaillé pour terminer la construction de la cité parmi les dangereux dédales de catacombes, tombes et donjons qu'Arthas avait entrepris.
