Esta igreja foi edificada no interior do antigo e destruído amuramento que protegeu o paço fortificado dos Condes do Redondo. No entanto, não existe um documento histórico conhecido que refira as suas origens e fundamentos. Terá sucedido à primeira igreja curada de Santa Maria, a qual já tinha existência paroquial no reinado de D. Dinis, em 1320. Pensa-se, segundo a arquitectura do edifício, que este terá sido construído no início do séc. XVI, no estilo arcaizante dos templos fortalezas (construção mudéjar-manuelina). A igreja encontra-se voltada para ocidente e apresenta um perfil acastelado, protegida por sete pequenas torres cilíndricas, de andares, sobrepujadas de cones estilizados; tem uma coroa de ameias do tipo muçulmano, de alvenaria grosseiramente rebocada. A porta travessa meridional é a primitiva, construída com rudes blocos de aparelho, com aro gótico, de chanfraduras, ábacos e capitéis esmagados para recobrimento de cal. Encontram-se, no mesmo alçado, alguns degraus e patim de acesso ao velho campanário exterior, em cujo flanco terminal e embebido na estrutura da torre, subsiste uma pequena torre lateral. A fachada tem formas rectilíneas, abastardas, e de frontão triangular, deficiente obra de alvenaria barroca, do séc. XVIII, tendo sido projectada para receber, angularmente, duas torres de secção quadrada. Apenas foi levantada a torre do lado sul, com pilastras e remate em cúpula, de aspecto popular. Nos acrotérios levantam-se grandes esferas de massa e no eixo uma tabela cega de cronograma sumido. O portal tem um janelão por cima, vasado em falso alpendre, sendo composto por vergas e jambas granitícas, da época de D. José e posterior ao terramoto de 1755. Lateralmente, embebida nos alçados, encontra-se uma antiga e tosca Via Sacra, em pedra. Na cornija dos beirais estão algumas gárgulas zoomórficas, em barro cozido, um trabalho de olaria popular alentejana. O interior é de três naves com abóbada de nervuras. No retábulo encontram-se quatro painéis de pintura a óleo da segunda metade do séc. XVI.

ESPANCA, Túlio, Igreja Matriz de S. Paulo de Pavia, in "A cidade de Évora", nº 51, pp. 167-173.

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

SANTOS, Reinaldo dos e PROENÇA, Raul, Guia de Portugal, vol. II, Lisboa, 1926.