A primitiva Igreja de São Paulo foi construída no século XV no espaço onde hoje está o largo. O terramoto de 1 de novembro de 1755 e o incêndio que se lhe seguiu destruíram grande parte do monumento.
A igreja foi reconstruída em 1768 segundo um projeto de traçado pombalino do arquiteto Francisco Remígio de Abreu.
Na fachada vemos um corpo central que é rematado por frontão triangular. Este é separado dos corpos laterais, as duas torres sineiras com relógio, por pilastras toscanas.
O corpo central contém três portas, sendo a central a maior com frontão curvo quebrado. No tímpano vemos um medalhão escultórico com "A Conversão de S. Paulo". As portas laterais, iguais entre si, são sobrepostas por áticas curvas encimadas por nichos com estátuas de S. Pedro e de S. Paulo.
O interior é composto por nave única com a capela-mor e 8 capelas laterais. O teto é de madeira pintada. No altar-mor existe um retábulo de mármore polícromo.
Na entrada da igreja existe um painel de azulejos do século XVIII representando S. Paulo.
Esta Igreja integra a Lisboa Pombalina, que está classificada como Conjunto de Interesse Público.