From the VIII century with the Muslim invasion of the Iberian Peninsula, Al’-Ulya is formed, said on the eve of the Christian Reconquista, in the chronicles of Ibne Saíde and Abd Aluhaid as a small almedina fortified and prosperous, belonging to the Kingdom Niebla, under the command of Taifa Ibne Mafom. This Almohad structure left us albarrana tower in mud (Torre da Vela – Sail Tower).
In 1249, the day of St. Clement, the forces of King Afonso III (1248-1279) conquered the town with the help of the Knights of Santiago, under the command of Master D. Palo Peres Correia. High the county seat by the charter of 1266, King Dinis donated the village and its fields to the Order of Santiago (1280), giving it later to a big fair, lasting a fortnight in the month of September (1291).
In the context of the 1383-1385 crisis, the village also faced difficulties, as Chamberlain chief witness João Afonso, whereby Loulé was quite depopulated, its castle was bleak walls and inside there were plenty of slums (Proceedings town council, 1385). Reports still that ran in the County the news that the forces of Castile were preparing to enter Portugal. Given the seriousness of the information and to guard against a possible attack, the town council decided to repair the tower surmounted the Faro door and up the walls and battlements of the southern flank around the village. Sensitive to this state of affairs, John I (1385-1433) granted special privileges to the Village term population to inhabit the inside of the fence and donated the slum opposite the Church of St. Clement, to build a churchyard.
With the cycle of the Portuguese Discoveries, the Algarve region, experienced a new surge of economic growth, which also benefited Loulé, exporting wine, olive oil, fruits and dry and salt fish. Thanks to these features, from 1422, the castle walls were rebuilt by Henry de Meneses, 1st Earl of Loulé.
During the Philippine Dynasty, the survey defenses Algarve made between the years 1617-1618 by the military engineer and architect Neapolitan Alexandre Massai, the Loulé Castle listed as having the most damaged walls in mud and noise (Description of the Kingdom of Algarve …, 1621).