Over de oorsprong van Albufeira is weinig bekend maar
men neemt aan dat op de plaatst waar nu de stad ligt, in prehistorische
tijden zich al een nederzetting bevond met een zeehaven.
De Romeinen installeerden zich in Albufeira op de “Cerro da Vila”,
een rotsformatie die, gelegen tussen de zee en de rivier Albufeira, een
bijna onneembaar schiereiland vormde. Ze noemden de plaats Baltum, het was
waarschijnlijk een kleine visserijhaven.
De Romeinen hadden een georganiseerde administratie zodat agrarische en commerciële activiteiten zich beter konden ontwikkelen. Ze bouwden aquaducten, straten en bruggen.
Toen de Arabieren de stad overnamen gaven ze haar de huidige naam Al-Buhera ("Kasteel van de Zee".) Het was een tijd van welvaart gebaseerd op landbouw en handel met Noord Afrika. Ze construeerden een degelijk verdedigingssysteem om de stad te beschermen tegen vijandige aanvallen door rondzwervende kruisvaarderbendes.
De introductie van nieuwe technieken en producten stimuleerde de landbouw.De Arabieren kenden de ploeg en het gebruik van mest. Gebruikmakend van nieuwe bevloeiingssystemen veranderden ze ongebruikt land in groentevelden en boomgaarden.
Na een korte eerste christelijke bezetting, in 1189 en1190, wordt Albufeira na de verovering van de stad door Dom Afonso III in 1249 opgenomen in het Portugese koninkrijk.
De vermindering van de zeehandel met de Islamitische staten aan de middellandse zee en de het daaropvolgende verval werd pas tweehonderd jaar later gevolgd door een periode van voorspoed in het tijdperk van de grote Portugese ontdekkingsreizen (15º en 16º eeuw).
In de 18º eeuw deden zich verscheidene aardbevingen voor.
De grootste was de grote aardbeving van Lissabon in 1755 en het verwoeste, verarmde Albufeira kon pas tegen het einde van de 19º eeuw zijn welvaart weer zien stijgen tengevolge van de groeiende visserij en visconserven industrie.
Het toerisme kwam in opkomst gedurende de 60´geer jaren en veranderde de stad in een belangrijke vakantieplaats.
Albufeira kreeg stadsrecht in 1986.