After the conquest the Normans set about latinising a Sicily that had been Byzantine and then Arab, founding abbeys and dioceses and endowing them with the widest feudal lordships. Monreale is the most ambitious instance of that policy. Since 1090 Palermo had held the island's only archbishopric, and in the 1170s William II chose to build, close to the capital and in a district where the Muslim presence was strongest, a monastery with a church attached.

The old charters give the site as Super Sanctam Kyriacam — above the small church of Santa Ciriaca. Local tradition says an Arab village called Balharā had stood on the ground. The legend the town tells is better: the Virgin appeared in a dream to William, resting under a carob tree after hunting, urging him to raise a temple in her honour and revealing where his father's treasure lay hidden. He had the tree uprooted, the treasure was found, and it paid for the cathedral.

The real reason was rivalry, personal as much as political, between the king and Palermo's English archbishop Gualtiero Offamilio — Walter of the Mill. A great ecclesia munita at Monreale threatened the Palermitan archdiocese directly, and it was meant to.

Construction began in the early 1170s — sources give 1172 and 1174 — and moved fast. Alexander III confirmed it in a bull of 30 December 1174 , and with two successive bulls, Attendentes quomodo (1174) and Ex debito suscepti regiminis (1175), granted the abbey extensive privileges and bound it directly to the Apostolic See. In 1176 the church dedicated to the Virgin — Santa Maria la Nuova — was handed over by the king to Benedictine monks obtained from the abbot of Cava de' Tirreni , who elected Teobaldo as their first abbot; he could wear episcopal insignia and enjoyed many privileges, and became a bishop shortly afterward.

The mosaics are the reason the building is famous, and they were made by the best available craftsmen, including Arab masters — the mastri di l'oru , the masters of gold. The complex comprises the basilica, the convent with its cloister , and the royal palace, and it now forms part of the UNESCO listing for Arab-Norman Palermo and the cathedrals of Cefalù and Monreale.

Much of what stands inside is later. In 1492 Cardinal Giovanni Borgia built the portal before the diaconicon and the sacristy; in 1595 Cardinal Ludovico II de Torres created the chapel of San Castrenze , where the relics of the city's and archdiocese's patron are kept in a silver urn; between 1687 and 1690 , at the will of Monsignor Roano and to a design by fra' Giovanni da Monreale, the chapel of the Crocifisso was raised; and in the first half of the eighteenth century the chapel of San Benedetto was opened. The cathedral's organ carries ten thousand pipes and is the only one in Italy with a six-manual console.

In the mountains behind, the Benedictine abbey of San Martino delle Scale has its own long history. The sixteenth-century historian Fazello attributes its foundation to Pietro Indulfo in 1182 , citing a privilege of King William, granted at Palermo in June of that year, donating the church of San Martino to the church of Monreale. Archbishop Emanuele afterward gave the place to the Benedictines on condition that they build a monastery and that every year, on 8 September , the Nativity of the Virgin, the monks process with lighted candles the two miles to Monreale.