Dopo la conquista, i Normanni si dedicarono a latinizzare una Sicilia che era stata bizantina e poi araba, fondando abbazie e diocesi e dotandole delle più vaste signorie feudali. Monreale ne è l'esempio più ambizioso. Dal 1090 Palermo deteneva l'unico arcivescovado dell'isola e, negli anni settanta del XII secolo, Guglielmo II scelse di costruire, vicino alla capitale e in un distretto dove la presenza musulmana era più forte, un monastero con annessa una chiesa.

Gli antichi documenti riportano il sito come Super Sanctam Kyriacam — sopra la piccola chiesa di Santa Ciriaca. La tradizione locale narra che sul terreno sorgesse un villaggio arabo chiamato Balharā . La leggenda raccontata dalla città è più bella: la Vergine apparve in sogno a Guglielmo, che riposava sotto un carrubo dopo una battuta di caccia, esortandolo a erigere un tempio in suo onore e rivelandogli dove fosse nascosto il tesoro di suo padre. Fece sradicare l'albero, il tesoro fu trovato e servì a pagare la cattedrale.

La vera ragione era la rivalità, tanto personale quanto politica, tra il re e l'arcivescovo inglese di Palermo Gualtiero Offamilio — Walter of the Mill. Una grande ecclesia munita a Monreale minacciava direttamente l'arcidiocesi palermitana, ed era questo l'intento.

La costruzione iniziò nei primi anni settanta del XII secolo — le fonti riportano il 1172 e il 1174 — e procedette rapidamente. Alessandro III la confermò con una bolla del 30 dicembre 1174 e, con due bolle successive, Attendentes quomodo (1174) ed Ex debito suscepti regiminis (1175), concesse all'abbazia ampi privilegi e la legò direttamente alla Sede Apostolica. Nel 1176 la chiesa dedicata alla Vergine — Santa Maria la Nuova — fu consegnata dal re ai monaci benedettini ottenuti dall'abate di Cava de' Tirreni , che elessero Teobaldo come loro primo abate; egli poté indossare le insegne episcopali, godette di molti privilegi e divenne vescovo poco dopo.

I mosaici sono la ragione per cui l'edificio è famoso e furono realizzati dai migliori artigiani disponibili, compresi i maestri arabi — i mastri di l'oru , i maestri dell'oro. Il complesso comprende la basilica, il convento con il suo chiostro e il palazzo reale, e oggi fa parte del sito UNESCO "Palermo arabo-normanna e le cattedrali di Cefalù e Monreale".

Gran parte di ciò che si trova all'interno è posteriore. Nel 1492 il cardinale Giovanni Borgia costruì il portale davanti al diaconico e alla sacrestia; nel 1595 il cardinale Ludovico II de Torres creò la cappella di San Castrenze , dove le reliquie del patrono della città e dell'arcidiocesi sono conservate in un'urna d'argento; tra il 1687 e il 1690 , per volontà di monsignor Roano e su progetto di fra' Giovanni da Monreale, fu eretta la cappella del Crocifisso; e nella prima metà del XVIII secolo fu aperta la cappella di San Benedetto. L'organo della cattedrale conta diecimila canne ed è l'unico in Italia con una consolle a sei manuali.

Sui monti retrostanti, l' abbazia benedettina di San Martino delle Scale ha la sua lunga storia. Lo storico cinquecentesco Fazello ne attribuisce la fondazione a Pietro Indulfo nel 1182 , citando un privilegio del re Guglielmo, concesso a Palermo nel giugno di quell'anno, che donava la chiesa di San Martino alla chiesa di Monreale. L'arcivescovo Emanuele donò in seguito il luogo ai Benedettini a condizione che costruissero un monastero e che ogni anno, l' 8 settembre , giorno della Natività della Vergine, i monaci percorressero in processione con ceri accesi le due miglia fino a Monreale.