La chiesa in cima alla collina è la chiesa principale di Tavira, e la maggior parte di quello che si vede è degli anni 1790. Il terremoto del 1755 la danneggiò gravemente, e il vescovo Francisco Gomes do Avelar la fece ricostruire dall'italiano Francisco Xavier Fabri come chiesa neoclassica. Ma il portale della facciata è gotico, del 1400 circa, e secondo le cronache la chiesa sorge dove si trovava la moschea maggiore della città quando l'Ordine di Santiago prese Tavira nel 1242. Nel coro riposano, dice la tradizione, Paio Peres Correia e i sette cavalieri la cui morte fu l'occasione della conquista. Che lui riposi davvero qui è discusso. La lapide merita comunque uno sguardo.
La cronaca dice che l'Ordine di Santiago fece della moschea maggiore la chiesa di Santa Maria quando prese Tavira, secondo la datazione corrente l'11 giugno 1242. Della moschea non è stato accertato nulla. La torre dell'orologio potrebbe essere il minareto: è quadrata e larga circa cinque metri, mentre i minareti modesti stavano sotto i tre. Ma un'incisione del Seicento mostra la facciata con due grandi torri, così nessuno sa se sia questa. Il coro guarda a est, e lo storico Luís Campos Paulo ne deduce che la chiesa fu costruita da zero; la moschea si trovava al massimo in parte sotto di essa.
Il portale principale, con quattro archivolti a sesto acuto e capitelli fogliati, è del 1400 circa e fu inserito nella nuova facciata dopo il 1755. Anche il coro e due cappelle laterali sono gotici. La Capela do Senhor dos Passos è manuelina, degli anni 1510, pagata da Lançarote de Melo, comendador dell'ordine; la volta ha chiavi araldiche e, all'imposta delle nervature, due draghi e una cintura con fibbia. Le visite dell'ordine dal 1554 in poi annotano rifacimenti: pilastri di pietra al posto di colonne di marmo, volte al posto di un tetto di canne.
La ricostruzione cominciò nel 1790 sotto il vescovo Francisco Gomes do Avelar su progetto dell'italiano Francisco Xavier Fabri, e il museo civico la chiama la più importante chiesa neoclassica dell'Algarve. Il retablo maggiore non è costruito ma dipinto: un trompe l'oeil attribuito a Joaquim José Rasquinho di Loulé, uno dei pochi in Algarve. Dietro di esso, nel 2021, si è trovata una camera di legno con un trono a gradini e pareti dipinte con il nome di Dio in ebraico, grano e uva, incompiuta e coperta per circa 200 anni.
Sul lato destro del coro c'è una lapide incisa per i sette martiri: il comendador-mor dell'ordine, cinque cavalieri e un mercante che, secondo la cronaca, furono uccisi a caccia presso Antas durante una tregua. Paio Peres Correia li vendicò e prese la città. La sua stessa lapide dice che morì il 10 febbraio 1275 e fu deposto qui nel 1751; le ossa erano state trovate intorno al 1724. La tradizione spagnola dice Talavera, poi Tentudía, e considera Tavira improbabile. È una storia migliore di quella certa.
Il portale è la parte più antica della facciata. Le stazioni della Via Crucis sono scolpite nella pietra sui muri esterni. All'interno, la lapide dei martiri è sul lato destro del coro, e il retablo maggiore sembra pietra ma è pittura. Il comune ha lavori al tetto in corso (poco meno di 400.000 euro), quindi parti della chiesa possono essere transennate. La chiesa fa parte della Rota dos Templos Marianos.
Sta in cima, dentro le mura del castello, perché lì c'era la moschea, nel punto più alto e meglio protetto della città. Tavira aveva, a quanto pare, una sola moschea, ampliata più volte. I conquistatori la purificarono, la dedicarono a Maria e vi posero un altare a san Barnaba, perché la città cadde nel suo giorno; la processione di ogni anno, l'11 giugno, è la fonte della data stessa. Quanto resti in piedi della moschea, nessuno può dirlo senza togliere l'intonaco dalla torre dell'orologio. Sandra Cavaco lo ha proposto. Non è successo.
La cosa interessante sono gli strati. Un portale gotico e un coro medievale, una cappella manuelina con draghi nella volta, azulejos del 1748, e attorno a tutto una chiesa neoclassica degli anni 1790 con un altare dipinto in modo da sembrare pietra. Dietro l'altare, una stanza che qualcuno abbandonò e coprì 200 anni fa. Perfino le tombe sono due storie: Paio Peres Correia ha una lapide qui e una tomba in Spagna. La chiesa è meno gotica della sua fama e più interessante di quanto sembri.