A igreja foi erigida sobre as ruínas da mesquita muçulmana logo após a Reconquista cristã de 1242, no alto terreiro que foi núcleo da povoação intra-muros. Foi a primeira paroquial de Tavira e dedicada a Nossa Senhora dos Mártires. Muito danificada pelo terramoto de 1755, foi mandada reedificar pelo bispo de Faro, D. Francisco Gomes de Avelar, e por ele foi de novo sagrada em 1800, mantendo-se a estrutura e o portal góticos.

A sua frontaria é marcada pelas fortes linhas das pilastras neoclássicas que ladeiam o portal e marcam as três naves do corpo da igreja e que nos cunhais são encimadas por pináculos de altas agulhas. A nave central é mais elevada, tendo no exterior um frontão triangular sobre ela e avançando a partir da frontaria, o corpo do portal gótico. Este, de quatro finas arquivoltas quebradas, arrancando de colunelos igualmente finos, decorados com capitéis vegetalistas (pâmpanos, folhas de hera, cardos), é rematado por um frontão interrompido com coruchéus de traço ainda barroco, datado da reconstrução setecentista. Nos três sectores definidos da frontaria abrem-se janelas semicirculares tripartidas. Entre os robustos contrafortes laterais, janelas semicirculares, semelhantes às da frontaria iluminam as naves abobadadas que constituem o espaço interior, dominado pela cor branca que reveste inclusivamente a cantaria. A cabeceira da igreja mantém o esquema dos inícios do séc. XIV, mas a ábside sofreu bastante com o terramoto, tendo perdido a abóbada de nervuras e as frestas.

O topo da capela-mor está totalmente preenchido por um retábulo dos finais do séc. XVIII que integra boas esculturas barrocas. Frente a este uma lápide também setecentista assinala o túmulo de D. Paio Peres Correia, falecido em Espanha em 1275 e sepultado em Tavira segundo a sua vontade, próximo dos túmulos dos seus cavaleiros mortos à traição no episódio que determinou a conquista de Tavira, e que estão assinalados por sete cruzes vermelhas de Santiago. Na absidíola sul subsistem uma janela gótica geminada, que remata numa pequena rosácea, e a cachorrada que apoia o beiral de cantaria. A absidíola norte conserva o seu arco gótico e uma abóbada ogival de nervuras, apoiada em colunas com capitéis fitomórficos. Na nave esquerda está situada a Capela do Senhor dos Passos, ainda manuelina, coberta por uma abóbada artesoada com a cruzaria em roseta em cujos bocetes estão representados a Cruz de Cristo, a Cruz de Sant'Iago e o brasão dos Melos, como motivos decorativos. As paredes estão revestidas de azulejos policromos e, ao fundo, na parte posterior (a parte anterior caiu com o terramoto), podem ver-se um retábulo em talha seiscentista e uma tribuna apainelada. A Capela do Santíssimo, construída em 1748, tem as paredes totalmente revestidas de bela azulejaria setecentista azul e branca (representando cenas rurais, a Ceia do Senhor, o Lava-pés, entre outras), e é coberta por uma cúpula. Na Capela do Senhor Morto subsiste uma abóbada ogival. A sacristia ostenta um admirável lavabo parietal datado de 1645, e é decorada por um silhar de azulejos setecentistas representando jarras de flores e cestos de frutos, enquadrados em molduras com enrolamentos de acanto. Fazem igualmente parte do recheio da igreja algumas peças escultóricas, sendo particularmente notáveis uma imagem gótica da Virgem, em madeira, provavelmente dos séculos XIV ou XV, e duas imagens setecentistas representando S. José e S. Lourenço. Entre as peças de ourivesaria destacam-se uma magnífica custódia do séc. XVIII com ornatos barrocos, um cálice do séc. XVI e dois do séc. XVII.

No exterior, uma escada dá acesso à torre sineira sul, coberta por um coruchéu em pirâmide quadrangular em cujos cunhais se erguem quatro pequenos pináculos. A norte, a torre do relógio, com mostradores invulgarmente grandes, tem uma traça muito diferente e conserva uma janela mudéjar. Em redor do edifício painéis de cantaria rematados por ornatos com volutas indicam as estações da Via Sacra. Foi nesta igreja que foram armados cavaleiros os filhos de D. João I após a conquista de Ceuta.

GIL, Júlio e CALVET, Nuno, As mais belas igrejas de Portugal, vol. I, Verbo, Lisboa, 1988.

LOPES, Flávio (coord.), Património Classificado - Arquitectónico e Arqueológico - inventário, vol. I, Lisboa, IPPAR, 1993.