マダバのモザイク地図は、西暦542年11月20日に奉献された新（ネア、Nea）教会のあるエルサレムを描写している。西暦570年より後に、エルサレムに建設された建物は描かれていないことから、モザイクの作成時期は西暦542-570年の内に限定される。モザイクはおそらく、その時代の主教所在地であったマダバのキリスト教集団における、知られざる芸術家により作られた。

614年に、マダバはサーサーン朝ペルシア帝国によって征服される。西暦8世紀には、ムスリムのウマイヤ朝指導者が、モザイクから人や動物の姿を描いた部分を除去した。746年、マダバの町は地震により大部分が崩壊し、その後放棄された。

19世紀後半にマダバには再び人が住むようになった。モザイクは1884年、古代の教会の跡地に、新しいギリシア正教会の教会が建設された際に発見された[1]。モザイク地図の大半は次の数十年のうちに、火災や新しい教会の活動、そして湿気の影響により破損した。1964年12月に、フォルクスワーゲン財団が、ドイツ・パレスチナ研究協会 (Deutscher Verein für die Erforschung Palästinas) に、モザイク保存のため 90,000 DM を賦与し、1965年には、考古学者の Heinz Cüppers および Herbert Donner が、モザイクの残された部分の修復および保存に着手した。