La carte montre l'église Néa Ecclésia à Jérusalem. Procope de Césarée évoque cette église et précise qu'elle a été construite par Justinien[1], donc entre 527, début du règne de celui-ci, et 561, date d'écriture de l'ouvrage. Cependant, on dispose d'informations encore plus précises, grâce à une inscription dédicatoire en grec gravée dans un réservoir sous l'église elle-même : « C'est là l'ouvrage que notre très pieux empereur Flavius Justinien a fait réaliser avec munificence, sous les auspices du très saint Constantin, prêtre et hegumen, en [l'an] 13 de l'indiction[2],[3] ». Donc la mosaïque est postérieure à 550, treizième année de l'indiction commencée en 536.

De plus, l'activité architecturale a été particulièrement développée à Madaba sous l'évêque Jean IV, entre 576 et la fin du siècle ; enfin, d'autres éléments comme la technique utilisée amènent à penser que la mosaïque date de la fin du VIe siècle[4],[5].

La mosaïque a été réalisée par des artistes inconnus, probablement sur l'initiative de la communauté chrétienne de la ville de Madaba qui était un évêché durant l'ère chrétienne byzantine. Au VIIIe siècle, les chefs musulmans ummayades font enlever certains des éléments figuratifs. En 614, Madaba est conquise par les Perses. En 746, la ville est fortement endommagée par un tremblement de terre. La ville, désormais vide d'habitants, décline.

En 1894, la mosaïque est retrouvée lors de travaux pour la construction d'un lieu de culte orthodoxe à l'emplacement de l'ancienne église byzantine. Dans les décennies qui suivirent, certaines parties de la mosaïque furent endommagées par des incendies, des éboulements, par l'action de l'eau et de l'humidité. En décembre 1964, la fondation Volkswagen met à disposition 90 000 DM pour la restauration de la mosaïque. Le directeur du rheinisches Landesmuseum de Trèves, Heinz Cüppers, et le spécialiste de l'Ancien Testament Herbert Donner mènent, de septembre à novembre 1965, les travaux urgents de restauration et de conservation des parties subsistantes de la mosaïque.