A primeira referência à Igreja Matriz de Quelfes remonta ao ano de 1518, à época uma ermida, que terá sido mandada construir por moradores locais e constituída por uma única nave e alpendre adossado à fachada principal.
Em 1534, inicia-se a construção da capela mor de estilo manuelino, terminada no mesmo ano.
A Igreja Matriz de Quelfes insere-se na tipologia de igrejas de transição do período manuelino para o período renascentista, de capela-mor quadrada com abobada de nervuras e três naves, construídas entre 1554 e 1565, quatro tramos e cobertura de madeira. Com grande qualidade escultórica, evidencia-se o arco triunfal manuelino muito decorado e a porta principal, já renascentista, com alçado triangular, enquadrada por duas pilastras lisas e capitéis de baços curvos.
O “Santuário Mariano”, publicado em 1716, referindo-se especialmente ao Santuário da Senhora do Rosário escreve de Quelfes o seguinte:
“No termo da Cidade de Faro, há uma freguesia, que intitulam Quelfez; não é lugar, são montes e herdades, e com moradores d’elas, os mais vizinhos, ficam a um tiro de espingarda; e a Paróquia vê-se situada entre Faro de onde dista uma légua, e o grande lugar de Moncarapacho e a Fortaleza de Olhão. É dedicada esta Paróquia ao glorioso Mártir S. Sebastião; e sendo Igreja de campo, é tão grande que podia ser Matriz de uma boa vila. Tem 4 altares alem do Altar-mor. Da parte do Evangelho, a primeira capela é dedicada à Conceição Puríssima de Maria, Nossa Senhora; a segunda é da Senhora do Rosário. Esta Santíssima imagem é muito moderna, porque não há mais do que 19 anos que se mandou fazer e se colocou naquela igreja. De outra parte da Igreja se vêem outras duas capelas a 1ª é de Santa Catarina, Mártir, e a 2ª do glorioso portuguez Santo António.”
Aquando do terramoto de Lisboa, em 1755, ficou fortemente danificada, com as partes superiores da fachada e a torre sineira em ruínas. Foi reconstruída com o contributo dos seus paroquianos, como afirma Francisco Gomes de Oliveira, “A Igreja desta freguesia padeceu ruína no terramoto de 1755, mas felizmente, está já reedificada devendo-se isso aos cuidados dos paroquianos da freguesia”.
A freguesia de Quelfes tem como orago S. Sebastião a quem dedica a sua Igreja Matriz.
