Der Ursprung von Albufeira ist nicht bekannt, aber
man nimmt an, dass wo heute die Stadt liegt, in prähistorischen Zeiten
eine wichtige Siedlung mit einem Seehafen existierte.
Die Römer machten sich sesshaft auf dem „Cerro da Vila“,
eine Felsformation, die eine fast unangreifbare Halbinsel zwischen dem Meer
und die Mündung des Flusses Albufeira bildete. Die Römer nannten
die Stelle Baltum. Sie brachten Ordnung und Organisation. Landwirtschaftliche
und kommerzielle Aktivitäten nahmen zu. Sie bauten Aquadukte, Straßen
und Brücken.
Als die Araber die Stadt übernahmen, gaben sie ihr ihren jetzigen Namen Al-Buhera ("Burg des Meeres ".) Es war eine Periode von Aufschwung basiert auf Landwirtschaft und Handel mit Nord Afrika. Sie bauten ein sehr gutes Verteidigungssystem und machten die Stadt fast uneinnehmbar. Die Verbesserung der Landwirtschaft war möglich durch die Einführung von neuen Techniken und den Anbau von anderen Produkte. Die Araber führten den Pflug und den Dünger ein, erstellten neue Bewässerungs-Systeme und verwandelten unbenutztes Land in Gemüsegärten und Obstplantagen.
Nach einen kurzen christlichen Besetzung, im Jahre1189 und 1190, wird Albufeira mit der Eroberung durch Dom Afonso III im Jahre 1249 entgültig in das Königreich Portugal integriert.
Das resultierende Wegfallen von dem Handel mit dem Mohammedaner Staaten führte zu einer Periode des Zerfalls. Einen neuen wirtschaftlichen Aufschwung entstand wieder während dem Zeitalter der Entdeckungen (15. und 16. Jahrhundert.)
Im 18. Jahrhundert wurde Albufeira durch Erdbeben heimgesucht, einschliesslich das Erdbeben von Lissabon im Jahre 1755, und verarmte. Erst Ende des 19. Jahrhunderts blühte die Wirtschaft durch Fischfang und Fischkonserven-Industrie wieder auf.
Der Tourismus-Boom begann in den 60ger Jahren und verwandelte die Stadt in einem wichtigen Ferienmetropole.
Albufeira bekam Stadtrechte im Jahre 1986.