Desconhecem-se as origens de Albufeira, mas tudo leva a crer que a região já era povoada em tempos pré-históricos e que o local onde hoje se ergue a cidade teria sido, alguns séculos antes da nossa era, uma importante povoação com o seu porto marítimo.

A primitiva povoação foi ocupada pelos Romanos que lhe deram o nome de Baltum. Introduziram uma organização administrativa centralizada e desenvolveram uma intensa actividade agrícola e comercial. Construíram aquedutos, estradas e pontes das quais ainda hoje existem vestígios.

O topónimo Albufeira provem da denominação árabe "Al-buhera" que significa "castelo do mar", razão que poderá estar ligada à proximidade do oceano e/ou da lagoa que se formava na zona baixa da localidade. Os árabes construíram sólidas fortificações defensivas, tornando-a quase inexpugnável, o que até certo ponto não era infundado, porque Albufeira foi uma das praças que os árabes conservaram por mais tempo em seu poder. O desenvolvimento da agricultura foi notável e verificou-se a introdução de novas técnicas e de novas culturas. Os Árabes usavam já a charrua e os adubos, assim como as noras para a elevação de águas nos poços. Introduziram novos sistemas de irrigação nos campos, salientando-se os açudes e levadas, transformando assim zonas incultas em hortas e pomares.

​Quando D.Afonso III ocupou o trono, já parte do Algarve tinha caído em poder dos cristãos. Templários e Hospitalários, ordens militares que auxiliaram na Reconquista, salteavam frequentemente as terras que ainda estavam sob domínio Árabe, mas detinham-se sempre diante das fortes muralhas de Albufeira. Somente depois da tomada de Faro é que a situação de Albufeira se tornou insustentável.

Cercada de inimigos por todos os lados, a praça caiu em poder de D.Afonso III, que imediatamente a doou à Ordem de Aviz.

Os mouros foram perseguidos de tal forma, que só escaparam ao furor dos vencedores os que fugiram e se refugiaram numa caverna, denominada Cova do Xorino, situada por baixo das rochas delimitantes da cidade pelo lado sul.

No reinado de D. Manuel I já a vila reconquistara a sua antiga importância, pois este monarca concedeu-lhe foral em 20 de Agosto de1504.

Albufeira foi das cidades algarvias a mais castigada por cataclismos naturais. Mas foi o terramoto e que causou os maiores estragos. O mar invadiu a vila com ondas que atingiram 10m de altura, destruindo quase todos os edifícios, tendo apenas ficado de pé 27 habitações e estas muito arruinadas.

A Igreja Matriz, antiga mesquita árabe adaptada ao culto cristão, onde a população se refugiara, pedindo misericórdia, desabou causando 227 vítimas. Depois deste terramoto continuou todo o Algarve a sofrer abalos violentos até 20 de Agosto do ano seguinte o que não impediu que se iniciassem de imediato as obras de reconstrução por ordem do Bispo D. Francisco Gomes de Avelar.

Em 1833, durante a guerra civil entre absolutistas e liberais, Albufeira foi cercada e atacada pelos soldados do Remexido: um chefe popular absolutista que danificou profundamente a vila e executou grande número dos seus habitantes.

A partir de meados do século XIX verificou-se um desenvolvimento da economia graças à actividade piscatória.

Nas primeiras décadas do século XX registou-se um aumento acentuado da exportação de peixe e de frutos secos. A vila tinha, então, cinco fábricas que empregavam 700 a 800 pessoas, sobretudo mulheres de pescadores.

De 1930 a 1960 registaram-se tempos de decadência, as armações de pesca arruinaram-se, as fábricas fecharam, as embarcações desapareceram e muitas casas foram abandonadas. A população ficou reduzida a metade e a pesca tornou-se novamente numa actividade de subsistência.

No início da década de 60, assistiu-se ao nascimento do fenómeno turístico, Albufeira foi procurada por turistas nacionais, mas foi sobretudo com os ingleses que prosperou.

Na década de 80, verificou-se um enorme surto urbanístico, tendo a cidade crescido para nascente, local para onde se transferiu a maior parte dos serviços administrativos, incluindo a Câmara Municipal.