Orixinalmente baixo a invocación de San Vicente de Saragoça, patrón da cidade de Lisboa, designada no século XVI polo nome de Baluarte de san Vicente a par de Belén e por Baluarte do Restelo, esta fortificación integraba o plano defensivo da barra do río Texo proxectado á época de Xoán II (1481-1495), integrado na marxe dereita do río polo Baluarte de Cascais e, na esquerda, polo Baluarte da Caparica.

O cronista García de Resende foi o autor do seu risco inicial, tendo rexistrado:

 

A estrutura comezaría a edificarse en 1514, baixo o reinado de Manuel I (1495-1521), tendo como arquitecto Francisco de Arruda. Localizábase sobre un afloramento rochoso nas augas do río, fronteiro á antiga praia de Belén, e destinábase a substituír a antiga nao artillada, ancorada naquel lugar, de onde partían as frotas para as indias. As súas obras ficaron a cargo de Diogo Boitaca, que nesa época tamén dirixía as xa adiantadas obras do veciño Mosteiro dos Xerónimos.

Concluída en 1520, foi o seu primeiro alcaide Gaspar de Paiva, nomeado para a función ao ano seguinte.

Coa evolución dos medios de ataque e defensa, a estrutura foi, gradualmente, perdendo a súa función defensiva orixinal. Ao longo dos séculos utilizouse como rexistro aduaneiro, posto de sinalización telegráfico, e farol. As súas polvoreiras foron usadas como alxubes para presos políticos durante o reinado de Filipe I (1580-98), e, máis tarde, por Xoán IV (1640-1656). O Arcebispo de Braga e Primado das Españas, Sebastião de Matos de Noronha (1636-1641), por coalición con España e facendo fronte a Xoán IV, foi preso e mandado recluso para a Torre de Belén.

Sufriu varias reformas ao longo dos séculos, principalmente a do século XVIII que privilexiou as ameas, o varandín do baluarte, e o recanto da Virxe cara ao río e o claustro.

Clasificada como Monumento Nacional por Decreto do 10 de xaneiro de 1907, foi declarada pola UNESCO como Patrimonio Cultural de toda a Humanidade no 1983.