En el mapa-mosaico de Madaba aparece la Iglesia Nea de Jerusalén, que se consagró el 20 de noviembre de 542. En la imagen no aparecen edificios construidos después del año 570, por lo que el período de tiempo en el que se creó el mapa queda limitado al comprendido entre esos dos años. El mosaico fue realizado por artistas anónimos, probablemente miembros de la comunidad cristiana de Madaba, donde en aquella época había un obispo. En 614, el Imperio persa conquistó Madaba. En el siglo VIII los gobernantes musulmanes de la dinastía Omeya, eliminaron algunas figuras del mosaico. En el año 746 un terremoto destruyó la mayor parte de Madaba, y la ciudad fue abandonada.

El mosaico se redescubrió en 1894, durante la construcción de una nueva iglesia ortodoxa en el lugar de la antigua. A lo largo de las décadas siguientes, varias partes del mosaico fueron dañadas por los incendios, las actividades en la nueva iglesia y los efectos de la humedad. En diciembre de 1964, la Fundación Volkswagen donó a la Deutscher Verein für die Erforschung Palästinas ("Sociedad Alemana para la Exploración de Palestina") 90.000 marcos para la conservación del mosaico. En 1965, los arqueólogos Heinz Cüppers y Herbert Donner llevaron a cabo la restauración de las partes del mosaico que se conservaban.