Originalment sota l'advocació de Sant Vicent màrtir, sant patró de Lisboa, anomenat el segle xvi pel nom de Baluard de Sant Vicent al costat de Betlem i Baluard Restelo, aquest fort era part del pla de defensa de la rivera del Tajo, projectat en l'època de Joan II de Portugal (1481-95), integrat al marge dret del riu per la Torre de Sant Antoni Cascais i a l'esquerra pel Fort de São Sebastião da Caparica.

El cronista Garcia de Resende va ser l'autor del seu risc inicial, de gravació:

I així llavors manà fer la torre i el baluard (...) de Caparica, enfront de Betlem, que hi havia molta i molt gran artilleria i que se li va ordenar de fer una forta fortalesa on avui hi ha la bonica Torre de Belém, que el Rei Manuel, que santa glòria tingui, ordenà fer, perquè la fortalesa d'una part i la torre de l'altre, tanquessin l'entrada del riu. Fortalesa la qual jo per ordres seves vaig dibuixar, i amb ell vaig manar a la seva voluntat, i ja havia donat la capitania que a Álvaro da Cunha, el seu cap del cavalleria, i persona de la seva confiança, i perquè el Rei Joan morí, no hi va haver temps per fer-se (Resende, García de. Crònica de Joao II, 1545.),

L'estructura només es va iniciar el 1514, sota el regnat de Manuel I de Portugal (1495-1521), amb l'arquitecte Francisco de Arruda. Es troba en un aflorament rocós del riu, davant la platja antiga de Betlem, i va ser destinat a substituir el vell vaixell d'artilleria, ancorat en aquest tram, on la flota va partir cap a les Índias. Les seves obres van ser encomanades a Diogo de Boitaca, que, en el seu moment, també va dirigir les obres des del veí primerenc Monestir dels Jerònims.

Completat el 1520, en fou el seu primer Alcalde Gaspar de Paiva, anomenat per aquesta funció l'any següent.

Amb el desenvolupament dels mitjans d'atac i defensa, l'estructura va perdre gradualment la funció defensiva original. Durant segles es va utilitzar per registrar l'estació de senyalització de duanes telègraf i far. El seu arsenal es va utilitzar com a calabós per als presos polítics durant el regnat de Felip II de Castella (1580-1598), i més tard per Joan IV de Portugal (1640-1656). L'arquebisbe de Braga i primat de les Espanyes, Sebastián de Matos de Noronha (1586-1641), per l'aliança d'Espanya i enfrontat a Joan IV de Portugal, va ser detingut i enviat com a presoner a la Torre de Belém.

Ha estat objecte de diverses renovacions al llarg dels segles, sobretot a partir del segle xviii que va afavorir les fortificacions, de les baranes de la fortalesa, la Fornícula de la Mare de Déu, davant del riu, i el claustre.

Classificat com un Monument Nacional pel decret de 10 de gener de 1907, és considerat com Patrimoni de la Humanitat per la UNESCO inscrit el 1983. Aquest mateix any es va unir a la XVII Exposició Europea d'Art de la Ciència i la Cultura.