Objectives: During the Middle Ages, Portugal witnessed unprecedented socioeconomic and religious changes under transitioning religious political rule. The implications of changing ruling powers for urban food systems and individual diets in medieval Portugal is poorly understood. This study aimed to elucidate the dietary impact of the Islamic and Christian conquests. Materials and Methods: Radiocarbon dating, peptide mass fingerprinting (ZooMS) and stable isotope analysis (δ13C, δ15N) of animal (n = 59) and human skeletal remains (n = 205) from Muslim and Christian burials were used to characterize the diet of a large historical sample from Portugal. A Bayesian stable isotope mixing model (BSIMM) was used to estimate the contribution of marine protein to human diet. Results: Early medieval (8–12th century), preconquest urban Muslim populations had mean (±1SD) values of −18.8 ± 0.4 ‰ for δ13C 10.4 ± 1 ‰ for δ15N, indicating a predominantly terrestrial diet, while late medieval (12–14th century) postconquest Muslim and Christian populations showed a greater reliance on marine resources with mean (±1SD) values of −17.9 ± 1.3‰ for δ13C and 11.1 ± 1.1‰ for δ15N. BSIMM estimation supported a significant increase in the contribution of marine resources to human diet. Discussion: The results provide the first biomolecular evidence for a dietary revolution that is not evidenced in contemporaneous historical accounts. We find that society transitioned from a largely agro-pastoral economy under Islamic rule to one characterized by a new focus on marine resources under later Christian rule. This economic change led to the naissance of the marine economy that went on to characterize the early-modern period in Portugal and its global expansion.