Les premières mentions indiscutables du nom Encaoua apparaissent dans des collections de responsa du XIIe siècle.
Un responsum particulièrement important, conservé dans la collection des teshuvot du Rav Yossef Ibn Migash (1077-1141), fait référence à un « Rav Choushan Encaoua ». Le Rav Yossef Ibn Migash, disciple de Rabbi Isaac Al-Fasi (le Rif) et maître de Maïmonide selon certaines traditions, dirigeait la yeshiva de Lucena. Le fait qu'un Encaoua corresponde avec cette autorité suprême du judaïsme ibérique atteste du rang élevé de la famille dès le XIIe siècle.
Un acte conservé à l'Archivo de la Corona de Aragón, daté de 1289, mentionne un « Mossé Encaoua » comme rabbin de la communauté juive (aljama) de Huesca. Les archives de la Couronne d'Aragon sont parmi les plus riches d'Europe pour documenter la vie des communautés juives médiévales. Les aljamas (communautés juives autonomes) disposaient de chartes royales leur garantissant une juridiction propre, et les rabbins y exerçaient des fonctions à la fois spirituelles et judiciaires.
Les mentions documentées des Encaoua dans plusieurs villes de la péninsule ibérique — Tolède, Séville, Saragosse, Huesca — révèlent une mobilité géographique caractéristique des élites rabbiniques médiévales. Les grands rabbins circulaient entre les aljamas au gré des nominations et des controverses halakhiques. Le réseau des communautés juives d'Espagne, qui comptait à son apogée au XIIIe siècle plus de 200 aljamas, fonctionnait comme un maillage intellectuel dense où les idées, les manuscrits et les controverses voyageaient avec les rabbanim. Le fait que des Encaoua soient attestés simultanément dans les royaumes de Castille (Tolède, Séville) et d'Aragon (Huesca, Saragosse) témoigne de l'ampleur de ce réseau familial dès le XIIIe siècle.
Après 1492, les archives de l'Inquisition espagnole fournissent, paradoxalement, des informations précieuses sur les familles juives d'avant l'expulsion. Les procès intentés aux conversos (Juifs convertis au christianisme) contiennent fréquemment des témoignages mentionnant les familles d'origine des accusés. Plusieurs dossiers conservés à l'Archivo Histórico Nacional de Madrid font référence à des « Abencava » ou « Encahua » parmi les familles dont l'orthodoxie chrétienne des descendants était mise en doute — preuve que le nom Encaoua était suffisamment connu pour attirer l'attention des inquisiteurs, et que certains membres de la famille avaient choisi la conversion plutôt que l'exil en 1492.