O actual forte foi edificado sobre diversas construções que remontam até ao antigo castelo árabe, cuja fundação se desconhece, apenas se sabendo que já existia no séc. XII.
Existem referências à edificação muçulmana pelo árabe Edrisi, que a menciona como a "Fortaleza da Mina".
Foi destruída por Iacube Al-Mansur e possivelmente edificada no reinado de D. Sancho II. São desconhecidos os traçados árabe e cristão e, através das crónicas de Fernão Lopes, apenas se pode deduzir que se trataria de uma construção típica do período medieval e implantada no local do actual forte.
Ignora-se também a data em que o castelo terá sofrido tranformações que lhe mudaram o aspecto, resultando uma fortaleza com canhoeira virada para o lado de terra e no lado fronteiro ao rio, adaptado à artilharia.
Ficou desactivada entre 1810 e 1831, altura em que as forças afectas a D. Miguel, resolveram reactivá-la, ficando em seu poder até 1833.
A sua importância só torna a ser de realce, com a inauguração da República.
Em 26 de Agosto de 1931, ocorre uma insurreição contra a ditadura vigente, na sequência um avião tentou destruir o forte, lançando uma bomba que veio a errar o alvo e que atingiu a urbe de Almada de que resultaram várias mortes.
Em 1936, na designada "revolta dos marinheiros", o forte de Almada e de Algés foram incumbidos de abrir fogo sobre os navios dos revoltosos.
A urbanização de Almada foi determinante na ineficácia do castelo, pois acabou por ser colocada na zona de tiro directo do conflito.

O castelo foi reconstruído em período anterior ao filipino, não suprimindo totalmente a anterior edificação medieval. Em 1666, a fortaleza foi ampliada por ordem do rei D. Afonso VI, sendo provável que as muralhas e a esplanada, onde se encontra o jardim público, sejam dessa época. Novas reparações foram realizadas devido aos danos causados pelo terramoto de 1755. Em 1810, a fortaleza ganha o aspecto geral que hoje se pode observar, sendo construídas linhas defesa da margem sul, de forma semi-circular. Em 1865-66, é reparado o paiol e construído um parapeito para a bateria e os alojamentos. As ameias resultam de uma intervenção recente.