As origens desta Igreja remontam à 2ª metade do século XIII. Em dezembro de 1298, a Igreja de S. Clemente passou para a Ordem Militar de São Tiago.
De acordo com os esquemas do Gótico Meridional, a planta é composta por três naves e três tramos cobertos de madeira, sem transepto e cabeceira de três capelas com abóbadas de cantaria. Os arcos são quebrados e os capitéis apresentam folhagem diversa bastante rudimentar.

No século XVI foram acrescentadas algumas capelas laterais e construídos cinco retábulos, destacando-se o da capela das Almas, cuja pintura figurativa foi contratada com Benaventura de Reis, em 1698. Edificada nos princípios do século XVI, na capela lateral evidencia-se o trabalho de cantaria tardo-medieval do arco de entrada e da abóbada. Sobre o altar construiu-se então um retábulo com seis painéis pintados, sendo o principal de Nossa Senhora da Piedade.

O século XVIII foi, na região algarvia, um período de grande prosperidade e forte implantação artística. Deste modo procedeu-se, nesta igreja, à renovação de todas as capelas.

A Confraria das Almas, para além de mandar revestir as paredes laterais de azulejos, encomendou ao mestre entalhador João Amado, em 1725, a feitura de um novo retábulo.

Em 1730, o Cardeal Pereira, Bispo do Algarve, como representante da Mitra, ajustou com João Amado a execução do retábulo para a capela-mor.

Nos princípios do século XVIII a Confraria de Nossa Senhora da Consolação promoveu a renovação interior da capela, resultando daí uma ambiência barroca de grande qualidade. É de salientar que a solução obtida é tipicamente portuguesa, sendo a azulejaria importada de Lisboa, talvez da oficina de Policarpo de Oliveira Bernardes. A talha deve-se a artistas locais, integrando-se o retábulo na tipologia mais utilizada no Algarve.

Nas capelas laterais do lado da epístola encontram-se vários retábulos. Dois deles foram mandados fazer no 3° quartel do século XVIII, por confrarias sediadas neste templo, sendo ambos duas importantes manifestações da talha rococó no Algarve.

Os dois retábulos, existentes nas ilhargas da capela mais profunda, foram aí colocados nos princípios deste século, depois de ter sido demolida a Igreja da Nossa Senhora do Carmo de Loulé.

O terramoto de 1755 danificou bastante esta igreja, particularmente as abóbadas da capela-mor, de uma capela colateral, da capela de S. Brás e ainda a torre.

Em 1856, um novo abalo provocou estragos na fachada, na cobertura e na sacristia da capela das Almas.

O sismo de 1969 obrigou a uma intervenção séria da Direção Geral de Edifícios e Monumentos Nacionais, que valorizou alguns elementos medievais ocultados na reconstrução oitocentista.

Foi classificada como Monumento Nacional pelo decreto n.º 9842, de 20 de junho de 1924.

De entre os testemunhos da arquitetura árabe na região algarvia aponta-se a torre, único elemento sobrevivente da mesquita de Loulé. Na opinião de Michel Terrasse a almádena foi construída no século XII pelos almóadas, servindo para o muezin chamar os crentes à oração. Após a Reconquista, foi adaptada ao culto cristão, tendo-se colocado na abóbada do campanário o brasão de armas português. No século XVI tinha dois sinos grandes e em cima um relógio.

Na Igreja Matriz de S. Clemente merece também referência o núcleo de imaginária religiosa dos séculos XVII e XVIII, sendo composto por duas dezenas de exemplares, uma parte das quais proveniente das extintas igrejas de Nª Sª do Carmo e do Convento da Graça de Loulé. Destacam-se as imagens de S. Brás, S. Clemente e S. Pedro (estes dois últimos com as vestes pontificais) do séc. XVIII, duas imagens que representam Nossa Senhora do Carmo - uma delas considerada notável - e a imagem de Nossa Senhora da Graça, padroeira do antigo convento do mesmo nome, com bom panejamento.

Em 2022, os trabalhos de reabilitação, num valor total de mais de 890 mil euros, visaram a recuperação e beneficiação do edifício, resolvendo as anomalias construtivas, funcionais, higiénicas e de segurança acumuladas ao longo dos anos. Estes trabalhos incidiram sobre as fachadas, coberturas, infraestruturas e torre sineira.

A intervenção contou ainda com o restauro dos retábulos e altares desta Igreja, assim como do pórtico do edifício.

A obra na Igreja Matriz de Loulé enquadra-se na política de recuperação e valorização do património arquitetónico e religioso que tem sido uma das linhas prioritárias da ação do Município de Loulé. 

LAMEIRA, Francisco; SERRA, Pedro, Igreja Matriz de S. Clemente. Loulé, Câmara Municipal, [s.d.].

CARRUSCA, Susana, Loulé: O património artístico. Loulé, Câmara Municipal, 2001, p. 75-77.