A cidade foi fundada pelos moabitas no seu reino, no século XIII a.C., a leste do rio Jordão. A cidade também foi habitada por muitas civilizações que governaram a região, entretanto, foi durante o domínio bizantino que ganhou maior relevância, pois as suas diversas igrejas históricas indicam que a cidade foi um dos centros cristãos mais importantes na Transjordânia. Os arredores de Madaba com seus sítios arqueológicos e lugares santos, como o Local do Batismo de Jesus, Monte Nebo, Maquero e Umm ar-Rasas transformaram a cidade num destino para peregrinos.
A história não diz claramente como o cristianismo se difundiu pelas cidades jordanianas, mas se fizermos uma leitura atenta dos Atos dos Apóstolos, veremos que alguns árabes se converteram no Pentecostes. Também há registo histórico da migração de cristãos para a cidade de Pella (Tabaqat Fahl), a leste da Jordânia. Se o cristianismo chegou à Antioquia, Ásia Menor e Roma ainda no tempo dos Apóstolos, é muito provável que já estivesse presente nas cidades jordanianas, como indicam os vestígios mais antigos do cristianismo encontrados na Palestina e na Jordânia, nomeadamente na cidade de Adir, próximo de Caraque, e que datam do final do primeiro século.
No ano 395, o imperador Teodósio dividiu a Palestina em três províncias: Palestina I, Palestina II e Palestina III, também chamada de Província Árabe, que inclui Neguev, parte do Sinai e Arabá. As cidades mais importantes da província incluíam Maquero, Madaba, Hisban, Amã, Jerash e Bosra. Em 330, a parte oriental do império recebeu o nome de Bizâncio e tornou-se a nova capital. Madaba, por sua vez, permaneceu na Província Árabe até ao momento em que foi conquistada pelos árabes. Essas divisões foram mantidas até o século X d.C.
No ano 325, o clero árabe, incluindo o Bispo de Madaba, participou do Primeiro Concílio Ecuménico de Nicéia. Segundo a história do cristianismo, o nome de Madaba é citado expressamente no Quarto Concílio Ecuménico, realizado em Calcedónia no ano 451, onde foi mencionado o nome do bispo: "Kaynós, Bispo de Madaba, cidade dos nabateus", além dos vinte bispos árabes que participaram do concílio. Tudo indica que o cristianismo está presente na Jordânia desde o tempo dos Apóstolos, e as comunidades de cristãos começaram a ser citadas em meados do século III.
Havia uma escola de mosaico em Madaba desde o tempo dos pagãos, para ensinar a arte do mosaico, a qual continuou a desenvolver-se na era cristã, uma vez que muitos mosaicos foram produzidos em Madaba, Nebo, al-Mukhayyat, Ma'in, al-Quwaysimah, entre outros. Embora os artesãos não tivessem o costume de assinar as suas obras, algumas obras perpetuaram os nomes de alguns deles, como Naoum, Kyriakos e Tomé na Igreja de São Jorge em Al-Mukhayyat; o monge Juliano, na Igreja do Padre João, em Al-Mukhayyat; o monge Elias, no Mosteiro Santa Maria, em Beisan; e Salomão, na Igreja dos Apóstolos, a quem é atribuído o mapa em mosaico de Madaba que imortalizou o nome da cidade no mundo da arte.
Pelo menos dez igrejas de Madaba possuem mosaicos que retratam a vida quotidiana no período bizantino, dos quais o famoso mapa na Igreja Ortodoxa Grega de São Jorge é o mais importante. Na Igreja dos Apóstolos, na área sul da cidade, também encontramos painéis magníficos que expressam a doutrina e o pensamento cristão, como a árvore da vida, a videira representando a Cruz de Cristo e o mistério da Eucaristia.
Esta arte prosperou em Madaba e nos seus arredores por séculos, até que um terramoto causou milhares de mortes e destruiu igrejas e mosteiros, no ano 746. O golpe final ocorreu em 1016, quando outro terramoto a deixou completamente destruída. No entanto, o que restou dessa arte mostra que os artesãos de Madaba eram comparáveis aos artesãos dos anos dourados do mosaico e que a sua arte é tão relevante quanto os melhores mosaicos do resto do mundo romano e bizantino.
Madaba na Bíblia Sagrada
Madaba foi citada na Bíblia pela primeira vez quando os hebreus deixaram a terra do Egipto e permaneceram por 40 anos no Sinai. Dali foram para o sul do Jordão, a fim de passar por Moab. Seon, rei dos amorreus, não permitiu e partiu para combater Israel que, por sua vez, o feriu com a espada, segundo as Escrituras: “Nós os crivámos de flechas; Hesebon está destruída até Dibon. Devastámos até Nofe, perto de Madaba" (Nm: 21-22). A palavra Madaba é uma palavra siríaca que significa "águas calmas" ou "águas de frutas".
O Livro de Josué narra que Madaba e os seus arredores foram dados aos rubenitas: “desde Aroer, que está situada na margem da torrente do Arnon, e desde a cidade que está no meio do vale e toda a planície de Madaba... Tais são as cidades e aldeias que couberam aos rubenitas, segundo as suas famílias" (Js 12:16-23). Madaba e as suas planícies férteis permaneceram palco de um conflito constante entre os habitantes e os invasores. A vitória ora era dos habitantes, ora dos invasores. Além disso, o Livro mencionou as vitórias de Mesa, rei dos moabitas, sobre Israel e a recuperação de Madaba, no século IX a.C.
Madaba era habitada por moabitas, apesar de ter ficado sob o domínio de alguns reinos vizinhos por um certo período de tempo. Ainda assim Madaba permaneceu moabita e local de culto a Camos, deus de Moab, como profetizado por Isaías no século VIII a.C., após a destruição causada pelo ataque assírio na segunda metade do século VIII (Is 15: 2-5). Os moabitas pediram refúgio ao rei de Judá enviando-lhe cordeiros como sinal de submissão (Is 16: 1-4). O Profeta Jeremias, por outro lado, narra a tragédia de Moab, que levou Moab a lamentar e chorar o seu passado de glória (Jr 48:31-32).