As origens desta Igreja remontam à 2ª metade do século XIII. É provável que o responsável pela encomenda tenha sido o Arcebispo de Braga, D. João Viegas que, em 1251, incumbiu os frades dominicanos de construir vários templos no Algarve.
No dia 4 de Dezembro de 1298, a Igreja de S. Clemente passou para a Ordem Militar de São Tiago por escambo feito entre o rei D. Dinis e o mestre da referida Ordem.
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. Todos estes exemplares foram retirados no século XVIII.
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 Direcção Geral de Edifícios e Monumentos Nacionais, que valorizou alguns elementos medievais adulterados na reconstrução oitocentista.
Foi classificada como Monumento Nacional pelo decreto n.º 9842, de 20 de Junho de 1924.
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 o já referido João Amado a execução do retábulo para a capela-mor.
A Confraria do Santíssimo Sacramento, depois das obras efectuadas na sua capela após a catástrofe de 1755, mandou fazer o retábulo em 1769.
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é.
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é.
Após a Reconquista, foram promulgados forais aos Mouros forros de Silves, Loulé, Faro e Tavira. Para além da agricultura, a actividade mais desenvolvida foi, sem dúvida, a manufactura do curtume de peles e do calçado.
Alguns séculos depois, encontramos nestas localidades confrarias de sapateiros, organizadas á volta de S. Crispim. Curiosamente constata-se a manutenção de um vocabulário profissional de origem árabe.
Em Loulé, a Confraria esteve muito activa no século XVII, data em que encomendou uma imagem de madeira do padroeiro. Pensa-se que foi feita por algum imaginário da região, pois ela atesta como o formulário maneirista aqui foi adoptado.
Esta capela lateral foi instituída nos princípios do século XVI por Gonçalo Mendes Caciro, conjugando-se no arco de entrada formas manuelinas com elementos renascentistas.
Em 1739 o mestre entalhador João Amado, então residente em Loulé, tomou por contrato a feitura de um retábulo de madeira de castanho para a capela de S. Brás. O referido mestre comprometia-se a fazê-lo durante dois anos de acordo “com todas as circunstâncias e regras da arquitectura da talha moderna” pelo preço de 240$000.
O retábulo existente coincide na sua maior parte com as cláusulas ajustadas, contudo não se insere em nenhuma das tipologias mais usadas na região algarvia, destacando-se o seu carácter pouco vulgar.
Edificada nos princípios do século XVI, nesta 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.
Nos princípios do século XVlll 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.
De entre os testemunhos da arquitectura á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. Posteriormente sofreu algumas modificações.
