O castelo medieval apresentava planta no formato quadrangular, com uma torre em cada vértice. Este perímetro fortificado corresponderia à alcáçova muçulmana. A povoação era acedida por três portas:

• a chamada "Porta da Praça" ou "Porta do Ocidente", que se constituía na porta principal, na altura da atual praça da República;
• a "Porta do Mar" ou "Porta da Praia", a Norte, onde subsiste um troço desse muralhamento, na atual rua Joaquim Pedro Samora; e
• a "Porta de Sant'Ana", assim chamada por dar acesso à Capela de Sant'Ana (desaparecida com o terramoto de 1755), situada um pouco mais abaixo, do lado direito do atual Posto da Guarda Fiscal. No século XVIII o culto de Sant'Ana passou a celebrar-se noutro templo, sob a mesma invocação.

A chamada Torre do Relógio, que atualmente se encontra integrada na edificação da Santa Casa de Misericórdia, na rua Bernardino de Sousa, era, primitivamente, uma das torres muçulmanas que defendiam a Porta da Praça, aí tendo funcionado a antiga cadeia. Ergue-se na muralha do castelo junto à antiga porta da Praça de Armas. Foi dotada no século XIX de uma coroa de ferro que sustenta o sino das horas.

Embora não se disponha de informação segura acerca da primitiva ocupação humana deste sítio, acredita-se que este trecho do litoral já era ocupado desde a pré-história por populações ligadas à coleta e àpesca. O seu porto teria propiciado a formação de uma povoação com alguma importância, que ao tempo da invasão romana da Península Ibérica se denominava "Baltum". A sua população, a par da atividade pesqueira, teria desenvolvido a agricultura e o comércio, trazendo um progresso económico do qual os vestígios de aquedutos, pontes eestradas são testemunho.

À época da invasão muçulmana da Península Ibérica, a partir do século VIII, teria sido fortificada, conforme atesta o seu topônimo árabe "al-Buhera" com o significado de "Castelo do Mar". Outros autores atribuem ao vocábulo o significado de "lagoa", então existente na parte baixa, que defenderia pelo lado de terra a península na qual a povoação se ergue.

A Albufeira islâmica constituía-se em um povoado amuralhado no topo da escarpa rochosa, que corresponde ao atual centro histórico, dominada por um castelo. A eficácia dessa defesa é atestada pelo fato de ter sido este um dos núcleos que mais tempo permaneceram no seu domínio.

À época da Reconquista cristã da península, após a conquista de Faro, a povoação de "Al-buhera" foi finalmente conquistada, em 1250, pelas forças de Afonso III de Portugal (1248-1279), sendo o castelo e os seus domínios doados pelo soberano aos cavaleiros da Ordem de Avis, na pessoa de seu Mestre, D. Martinho Fernandes (1 de março de 1250).

Embora não haja informação disponível, é possível que as suas defesas tenham, a partir de então, sido recompostas. É certo que a povoação se desenvolveu nos séculos seguintes, uma vez que à época de Manuel I de Portugal (1495-1521), recebeu Foral (20 de agosto de1504). Embora também não haja informação, as suas defesas devem ter sido reforçadas nesse período.

Localizada em uma falésia, a povoação foi desde sempre atingida pelos cataclismos naturais. Foi particularmente castigada pelo terramoto de 1755, cujo maremoto consequente atingiu a costa naquele trecho com ondas de mais de dez metros de altura, arrasando tudo à sua passagem. Na vila permaneceram de pé apenas 27 casas de habitação. A Igreja Matriz, na qual se refugiara parte da população, desabou, causando 227 vítimas. Embora tivessem sido iniciadas de imediato obras para reparação dos danos, a região continuou sendo sacudida por terramotos até agosto do ano seguinte.

Em 1833, à época da Guerra Civil Portuguesa (1828-1834), a vila foi cercada e tomada de assalto pelas forças de José Joaquim de Sousa Reis (o "Remexido"), um capitão de guerrilhas miguelista, causando extensos danos materiais. A luta teve um saldo de cerca de 27 mortos entre ambos os lados.

Entre o século XIX e o XX, a vila conheceu surtos de crescimento e depressão económica. Modernamente, graças ao turismo, um expressivo surto de progresso se instalou. Pouco resta, entretanto, dos antigos muros medievais da vila, que não resistiram ao progresso urbano, demolidos na década de 1960 quando da construção do "Hotel Sol e Mar". Esses remanescentes não se encontram classificados nem em vias de classificação pelo poder público português.