A linhagem “Correia” tem início mitológico no senhor de Farelães (Braga) Elio Saia (1004) e documentado no seu trineto Paio Ramiro, natural e senhor de Farelões, rico-homem de D. Afonso VI de Leão (1065-1109). Foi pai de Soeiro (Felgueiras Gaio, 1678).
Soeiro Pais Correia, contemporânio do Conde de Portugal D. Henrique (1096-1112), foi o primeiro do apelido “por se sustentar com elas no apertado cerco que os Mouros lhe puzeram no cerco de Monte Mor-o-Velho”. Foi casado com Urraca Hueris, filha de Huer Gueda e tiveram Paio.
Paio Soares Correia “o Velho” casou com Gontinha Godins e 2ª vez com Maria Gomes da Silva, filha de Gomes Pais da Silva e Urraca Nunes Velho. Do 2º matrimónio nasceu Pedro.
Pedro Pais Correia no couto do mosteiro de Roriz “fez umas casas que lhe quiseram impedir os Priores dele, pelo que lhe matou dois religiosos”. Casou com Dordia Peres de Aguiar, filha de Pero Huereis de Aguiar e Estevainha Mendes de Gundar. Foram pais de Paio e de outros nove que continuaram o apelido.
Paio Peres Correia, como comendador da Ordem de Santiago de Espada, ao serviço de D. Sancho II, participou na reconquista de Aljustrel (1234), Mértola (1238), Estômbar e Alvôr (1238) que foram trocadas por Cacela, Tavira, Castro Marim, Salir, Silves e Paderne (1242). Como mestre dos Espatários, ao lado de D. Afonso III, concluiu a reconquista do Reino d’al Garbe (1249) – Faro, Loulé, Porches e Aljezur (Crónica da Conquista do Algarve, c.1340). Faleceu em 1275 e jaz na Igreja de Santa Maria do Castelo de Tavira com sete cavaleiros cuja morte originou a conquista da cidade.
O apelido Correia vem referido nas Actas de Vereação de Loulé (2004):
- Diogo Mendez Corea (1492-96) cavaleiro da Cassa d‘el Rey D. João II, contador das obras e das terças do Reino do Algarve, juíz dos resíduos e provedor dos órfãos;
- Martim Correia, Bastiam Correia e Joham Martinz Correia, codrilheiros da vintena de Alte (1494);
- Afonso Correia (1494-96) codrilheiro, escudeiro, vereador e procurador do povo miúdo.
