Nel medioevo, il luogo, dove è situata la chiesa, era ricco di giardini ed orti a meridione della città allora edificata. 
La “Mansio Sanctae Trinitatis”, appartenuta ai Cavalieri Teutonici dal 1197 al 1492, sorse intorno alla metà del XII secolo. 

Essa rappresenta uno degli ultimi prodotti dell’architettura siciliana dell’età normanna. Il complesso fu ampliato nel secolo XV secolo, fino ad assumere vaste proporzioni; la chiesa fu innalzata a Commenda nel 1492 e vi furono aperte alcune cappelle laterali. In epoca barocca la chiesa era stata coperta da uno spesso strato di intonaco che nascondeva la struttura originaria. 

L’immagine odierna del monumento e il risultato dei drastici restauri effettuati tra il 1875 e gli anni venti del XX secolo che hanno completamente decurtato le sovrapposizioni successive, nell’intento di ripristinare l’originario monumento tardo-normanno. Si accede al complesso attraverso il portale barocco costruito nel 1717 all’ingresso del giardino antistante la chiesa. Internamente la chiesa presenta la snellezza propria dello stile gotico, con gli archi ogivali sostenuti da colonnati. 

Di mirabile fattura le opere d’arte presenti, sebbene non contemporanee alla realizzazione della chiesa. Sul lato settentrionale, è posto un Chiostro che mantiene due delle originali corsie del portico ad arcate ogivali, impostate su coppie di colonne dagli eleganti capitelli. Alle spalle del battistero si trova un Oratorio barocco con altare in marmi mischi e Crocifisso seicentesco.