La chiesa di S.Maria viene menzionata per la prima volta in un diploma del re Ruggero il Normanno, risalente al 1115, secondo alcuni, e al 1130, secondo altri. Recenti indagini hanno accertato che la parte più antica della costruzione poggia "su un complesso rupestre alto-medievale", di cui la vicina cripta dello Spirito Santo costituisce la testimonianza più remota; essa conserva ancora, intagliati nella roccia, un altare, croci e loculi di derivazione greca. Maggiore consistenza storica viene data generalmente ad un altro diploma, più tardo, del 1308, anno in cui S.Maria viene citata fra i beni del " casale et castrum Militelli ".
La chiesa incominciò ad accrescersi a partire dalla seconda metà del XV secolo, quando venne eretto il campanile. Nel 1506 con la definitiva sistemazione della porta maggiore, poteva dirsi in massima parte completata, anche se mancava ancora la cuspide del campanile, che sarebbe stata innalzata soltanto un secolo più tardi.
All' interno della chiesa, ridotta ad una sola navata dal terribile terremoto del 1693, si fa ammirare il decoratissimo altare della Natività (XVII secolo), che ostenta i suoi ricami nelle colonne, nel frontone e nel paliotto della mensa. In un altro altare invece, un frammento marmoreo che raffigura l' Annunciazione , si fa risalire al XV secolo.

Di impianto quattrocentesco è infine la cappelletta quadrangolare, adibita a sagrestia, dietro l'altare maggiore, con volta a costoloni.Il portale, protetto da un portico sostenuto da due leoni stilofori, rimane il capolavoro-simbolo di questa chiesa.  
Al centro della composizione, nella lunetta, spicca la Madonna con il Bambino , adorata da due angeli e sormontata da una stella. Negli stipiti una schiera di profeti e sibille , e nella cuspide l' Incoronazione d ella Vergine . L'opera è probabilmente un lavoro giovanile di Antonello Gagini.