La iglesia en lo alto de la colina es la iglesia principal de Tavira, y la mayor parte de lo que se ve es de la década de 1790. El terremoto de 1755 la dañó gravemente, y el obispo Francisco Gomes do Avelar encargó al italiano Francisco Xavier Fabri reconstruirla como iglesia neoclásica. Pero la portada de la fachada es gótica, de hacia 1400, y según las crónicas la iglesia se alza donde estaba la mezquita mayor de la ciudad cuando la Orden de Santiago tomó Tavira en 1242. En la capilla mayor yacen, dice la tradición, Paio Peres Correia y los siete caballeros cuya muerte fue el motivo de la conquista. Que él repose aquí de verdad es discutido. La lápida merece verse de todos modos.
La crónica dice que la Orden de Santiago convirtió la mezquita mayor en la iglesia de Santa Maria cuando tomó Tavira, según la datación habitual el 11 de junio de 1242. De la mezquita no se ha comprobado nada. La torre del reloj puede ser el alminar: es cuadrada y de unos cinco metros de ancho, cuando los alminares modestos no llegaban a tres. Pero un grabado del siglo XVII muestra la fachada con dos grandes torres, así que nadie sabe si es esta. La capilla mayor mira al este, y el historiador Luís Campos Paulo deduce de ello que la iglesia se construyó desde cero; la mezquita quedaba, como mucho, en parte debajo de ella.
La portada principal, con cuatro arquivoltas apuntadas y capiteles de hojas, es de hacia 1400 y se integró en la nueva fachada después de 1755. La capilla mayor y dos capillas laterales también son góticas. La Capela do Senhor dos Passos es manuelina, de la década de 1510, pagada por Lançarote de Melo, comendador de la orden; la bóveda tiene claves heráldicas y, en los arranques de los nervios, dos dragones y un cinturón con hebilla. Las visitas de la orden desde 1554 en adelante anotan reformas: pilares de piedra en lugar de columnas de mármol, bóvedas en lugar de techumbre de cañizo.
La reconstrucción empezó en 1790 bajo el obispo Francisco Gomes do Avelar según el proyecto del italiano Francisco Xavier Fabri, y el museo municipal la llama la iglesia neoclásica más importante del Algarve. El retablo mayor no está construido, sino pintado: un trampantojo atribuido a Joaquim José Rasquinho, de Loulé, uno de los pocos del Algarve. Detrás de él se encontró en 2021 una cámara de madera con un trono de gradas y paredes pintadas con el nombre de Dios en hebreo, trigo y uvas, inacabada y tapada durante unos 200 años.
En el lado derecho de la capilla mayor hay una lápida grabada a los siete mártires: el comendador-mor de la orden, cinco caballeros y un mercader que, según la crónica, fueron asesinados mientras cazaban en Antas durante una tregua. Paio Peres Correia los vengó y tomó la ciudad. Su propia lápida dice que murió el 10 de febrero de 1275 y que fue depositado aquí en 1751; los huesos se habían encontrado hacia 1724. La tradición española dice Talavera, luego Tentudía, y considera Tavira improbable. Es una historia mejor que la segura.
La portada es la parte más antigua de la fachada. Las estaciones del vía crucis están talladas en piedra en los muros exteriores. Dentro, la lápida de los mártires está en el lado derecho de la capilla mayor, y el retablo mayor parece piedra, pero es pintura. El ayuntamiento tiene obras en la cubierta en marcha (poco menos de 400.000 euros), así que partes de la iglesia pueden estar acordonadas. La iglesia forma parte de la Rota dos Templos Marianos.
Está en lo más alto dentro de la muralla del castillo porque allí estaba la mezquita, en el punto más elevado y mejor protegido de la ciudad. Tavira tuvo, según todos los indicios, una sola mezquita, ampliada varias veces. Los conquistadores la purificaron, la dedicaron a María y levantaron un altar a san Bernabé, porque la ciudad cayó en su día; la procesión de cada año el 11 de junio es la fuente de la propia fecha. Cuánto queda en pie de la mezquita, nadie puede decirlo sin picar el revoco de la torre del reloj. Sandra Cavaco lo ha propuesto. No ha ocurrido.
Lo interesante son las capas. Una portada gótica y una capilla mayor medieval, una capilla manuelina con dragones en la bóveda, azulejos de 1748 y, en torno a todo ello, una iglesia neoclásica de la década de 1790 con un altar pintado para que parezca piedra. Detrás del altar, una sala que alguien abandonó y tapó hace 200 años. Hasta las tumbas son dos historias: Paio Peres Correia tiene una lápida aquí y una tumba en España. La iglesia es menos gótica que su fama y más interesante de lo que suena.