A igreja no alto da colina é a igreja matriz de Tavira, e a maior parte do que se vê é da década de 1790. O terramoto de 1755 danificou-a gravemente, e o bispo Francisco Gomes do Avelar mandou o italiano Francisco Xavier Fabri reconstruí-la como igreja neoclássica. Mas o portal da fachada é gótico, de cerca de 1400, e segundo as crónicas a igreja ergue-se onde ficava a mesquita maior da cidade quando a Ordem de Santiago tomou Tavira em 1242. Na capela-mor jazem, diz a tradição, Paio Peres Correia e os sete cavaleiros cuja morte foi o motivo da conquista. Se ele jaz mesmo aqui, é discutido. A lápide merece ser vista na mesma.
A crónica diz que a Ordem de Santiago fez da mesquita maior a igreja de Santa Maria quando tomou Tavira, segundo a datação corrente a 11 de junho de 1242. Da mesquita nada foi comprovado. A Torre do Relógio pode ser o minarete: é quadrada e tem cerca de cinco metros de largura, quando os minaretes modestos tinham menos de três. Mas uma gravura do século XVII mostra a fachada com duas grandes torres, e por isso ninguém sabe se é esta. A capela-mor está virada a nascente, e o historiador Luís Campos Paulo conclui daí que a igreja foi construída de raiz; a mesquita ficava, quando muito, parcialmente debaixo dela.
O portal principal, com quatro arquivoltas ogivais e capitéis de folhagem, é de cerca de 1400 e foi integrado na nova fachada depois de 1755. A capela-mor e duas capelas laterais também são góticas. A Capela do Senhor dos Passos é manuelina, da década de 1510, paga por Lançarote de Melo, comendador da ordem; a abóbada tem fechos heráldicos e, nos arranques das nervuras, dois dragões e um cinto com fivela. As visitações da ordem a partir de 1554 registam obras: pilares de pedra em vez de colunas de mármore, abóbadas em vez de cobertura de caniço.
A reconstrução começou em 1790 sob o bispo Francisco Gomes do Avelar, segundo o projeto do italiano Francisco Xavier Fabri, e o museu municipal chama-lhe a mais importante igreja neoclássica do Algarve. O retábulo-mor não é construído, é pintado: um trompe l'oeil atribuído a Joaquim José Rasquinho, de Loulé, um dos poucos no Algarve. Atrás dele encontrou-se em 2021 uma câmara de madeira com um trono de degraus e paredes pintadas com o nome de Deus em hebraico, trigo e uvas, inacabada e tapada durante cerca de 200 anos.
Do lado direito da capela-mor está uma lápide gravada aos sete mártires: o comendador-mor da ordem, cinco cavaleiros e um mercador que, segundo a crónica, foram mortos numa caçada junto às Antas durante uma trégua. Paio Peres Correia vingou-os e tomou a cidade. A sua própria lápide diz que morreu a 10 de fevereiro de 1275 e que foi aqui depositado em 1751; os ossos tinham sido encontrados por volta de 1724. A tradição espanhola diz Talavera, depois Tentudía, e considera Tavira improvável. É uma história melhor do que a certa.
O portal é a parte mais antiga da fachada. As estações da Via-Sacra estão esculpidas em pedra nas paredes exteriores. No interior, a lápide dos mártires fica do lado direito da capela-mor, e o retábulo-mor parece pedra mas é pintura. A Câmara tem obras na cobertura em curso (pouco menos de 400.000 euros), pelo que partes da igreja podem estar vedadas. A igreja integra a Rota dos Templos Marianos.
Fica no ponto mais alto dentro da muralha do castelo porque a mesquita ficava ali, no sítio mais elevado e mais bem protegido da cidade. Tavira teve, ao que tudo indica, uma única mesquita, ampliada várias vezes. Os conquistadores purificaram-na, dedicaram-na a Maria e ergueram um altar a São Barnabé, porque a cidade caiu no dia dele; a procissão de cada ano a 11 de junho é a fonte da própria data. Quanto da mesquita ainda está de pé, ninguém o pode dizer sem picar o reboco da Torre do Relógio. Sandra Cavaco propôs isso. Não aconteceu.
O interessante são as camadas. Um portal gótico e uma capela-mor medieval, uma capela manuelina com dragões na abóbada, azulejos de 1748 e, à volta de tudo isto, uma igreja neoclássica da década de 1790 com um altar pintado para parecer pedra. Atrás do altar, uma sala que alguém abandonou e tapou há 200 anos. Até as sepulturas são duas histórias: Paio Peres Correia tem uma lápide aqui e uma sepultura em Espanha. A igreja é menos gótica do que a sua fama e mais interessante do que isso parece.