Le vide laissé par les Romains a été occupé par des envahisseurs barbares venus de l’autre côté des Pyrénées : Vandales, Alans, Wisigoths et Souabes. Finalement, ce sont les Wisigoths aryens, déjà convertis au christianisme, qui ont fini par dominer le territoire en 469.
Les querelles internes des Wisigoths ont conduit à l’arrivée de la grande vague d’envahisseurs suivante, les Arabes d’Afrique du Nord en 711, lorsqu’une faction wisigothe leur a demandé de l’aide. Ils ont rapidement occupé une partie de la côte sud du Portugal.
Les habitants de cette région ont connu la paix et la prospérité sous la domination des musulmans, qui ont établi leur capitale à Shelb (Silves). Les nouveaux dirigeants étaient tolérants envers les juifs et les chrétiens ; ils ont permis aux petits propriétaires chrétiens de conserver leurs terres et les ont encouragés à essayer de nouvelles méthodes et cultures, en particulier le riz et les agrumes. La langue portugaise actuelle comporte de nombreux mots d’origine arabe et de nombreux noms de lieux, dont Fatima, Silves et Algarve, et les pâtisseries traditionnelles ont une influence musulmane certaine.
Pendant ce temps, au nord, les troupes chrétiennes se renforcent et conquièrent Porto en 868, bien que la Reconquête n’atteigne son apogée qu’au XIe siècle. En 1064, Coimbra tombe et en 1085, Alphonse VI de Castille bat les musulmans à Tolède, leur enclave centrale en Espagne, bien que l’année suivante, les troupes d’Alphonse soient expulsées par les Almoravides belliqueux qui viennent au secours de l’émir depuis ce qui est aujourd’hui le Maroc.
En réponse à l’appel au secours du roi de Castille, de nombreux croisés européens sont venus combattre les infidèles. Avec l’aide d’Henri de Bourgogne, entre autres, Alfonso fait des progrès décisifs. La lutte se poursuit pendant plusieurs générations et, en 1139, Alfonso Enriquez (petit-fils d’Alfonso VI) remporte une victoire décisive en Ourique (Alentejo), se proclame Dom (roi) et reconquiert Santarem et Lisbonne. C’est la naissance du royaume du Portugal. À sa mort en 1185, la frontière portugaise est sécurisée jusqu’au Tage, mais il faut encore un siècle pour que le sud soit pris aux musulmans.