É ponto assente que o Cristianismo entrou no território que é hoje Portugal pelo sul, possivelmente por influência das igrejas do norte de África. A documentação é escassa, mas suficiente para datar da época romana, pelo menos do século III, a cristianização de Ossónoba (nome de Faro até quase ao fim da época muçulmana), dado que Vicente, Bispo desta cidade, assina em 8º lugar as atas do Concílio de Elvira (304). Há, pois, em Faro, desde os primórdios do século IV, uma hierarquia episcopal. Por sua vez, as atas dos Concílios hispânicos e testemunhos arqueológicos locais evidenciam a implantação e a vitalidade da Igreja do Algarve durante o período visigótico. Com a invasão muçulmana, a Igreja conheceu restrições de liberdade e, por vezes, até, alguma perseguição, a par de outros momentos de coexistente tolerância.

A vida cristã, não obstante, persistiu. Autores muçulmanos testemunham-no pelas referências às peregrinações de cristãos moçárabes aos santuários de São Vicente (desde o século VIII, no cabo do mesmo nome) e de Santa Maria de Ossónoba (cantada por Afonso X, em vésperas da conquista cristã). Os portugueses entraram no Algarve como conquistadores e ignoraram a Igreja existente no território conquistado que era de expressão e rito moçárabes. Criaram um Bispado em Silves, primeiro em 1189, que se manteve apenas dois anos; depois, em 1251, que substituiu a antiga Sé de Santa Maria de Faro. De entre os Bispos de Silves, entre outros, destaca-se D. Álvaro Pais (1333-1350). Perante a decadência de Silves e a crescente importância do litoral, o Bispo D. Manuel de Sousa, de acordo com o rei D. João III, pediu, em 1538, a transferência da Catedral de Silves para Faro.

Pela Bula Sacrossancta Romana Ecclesia de 20-10-1539, o Papa Paulo III deu assentimento a este pedido. Mas, o regresso à primitiva Igreja Catedral de Santa Maria de Ossónoba-Faro, só veio a efetuar-se em 30-03-1577, durante o episcopado de D. Jerónimo Osório, grande humanista e teólogo português. As Ordens religiosas, tanto masculinas como femininas, desenvolveram uma notável ação no Algarve, sobretudo ao longo dos séculos XVI a XVIII, tendo possibilitado a participação de muitos missionários algarvios na evangelização dos territórios descobertos pelos portugueses. A sua extinção veio, porém, interromper essa ação, tanto dentro como fora da Diocese, contribuindo para o vazio que ainda hoje se faz sentir.

A Diocese do Algarve foi, sucessivamente, sufragânea de Mérida, São Tiago de Compostela, Braga, Sevilha, Lisboa e, por último, desde 29-09-1540, de Évora. O seu território corresponde ao do antigo Reino do Algarve e, atualmente, ao do Distrito de Faro, com 5071,60 Km² de superfície e uma população de sensivelmente 400 000 residentes habituais, registando-se uma notável subida na época alta do turismo.