La primera expedición española que llegó a las costas de Veracruz, en 1518, estaba al mando de Juan de Grijalva, quien desembarcó en un islote al que bautizó con el nombre de San Juan de Ulúa; San Juan por ser 24 de junio –día de San Juan Bautista-, y Ulúa porque creyó oír pronunciar a los naturales que ahí se encontraban las palabras de úlua o colúa. El 21 de abril de 1519 llega la segunda expedición que fondeó junto a San Juan de Ulúa, dirigida por Hernán Cortés quien, tocando tierra firme frente a la isla, fundó la Villa Rica de la Vera Cruz y nombró un ayudante provisional.
La isla de San Juan de Ulúa era el punto más protegido del Golfo; de ahí se trasladaba a viajeros y carga en pequeñas barcazas a tierra firme; así, San Juan de Ulúa era un paso forzoso para llegar a la Nueva España. De esta manera comenzaron a levantarse construcciones que sirvieron para proteger a la flota de los enemigos tanto humanos como naturales.
Hacia 1552 existía en el islote una pequeña torre no mayor que la altura de un hombre. Para fines del siglo XVI, la Torre Vieja formó complemento de un muro de argollas y un baluarte en su extremo que protegía a la flota real naviera de los vientos impetuosos del norte.
En 1681 la Junta de Guerra nombró al ingeniero Jaime Franck para que proyectara y construyera la fortaleza de San Juan de Ulúa complementando las primeras estructuras al recinto, plan que aceptó en 1689 el virrey de Monclova.
Años después se complementaron algunos elementos de la fortaleza: el baluarte de la Soledad fue terminado en 1707, y en 1710 la torre del Caballero Alto, en el baluarte de San Crispín.
Durante la guerra de Independencia sirvió como baluarte a las fuerzas españolas y fue su último reducto, ya que después de arduos combates, el general Miguel Barragán logró que sus defensores capitularan en 1825.
En las primeras décadas del México independiente, y debido a los continuos cambios de poder, la fortaleza estuvo llena de presos políticos, entre ellos algunos compatriotas notables, como Benito Juárez, Melchor Ocampo, los frailes Servando Teresa de Mier y Melchor de Talamantes. Más tarde, en el gobierno de Porfirio Díaz, su celebridad como prisión aumentó, ya que en ella se confinó a miles de ciudadanos; de esa época data la reclusión de "Chucho el Roto" y la demolición de algunas partes de la construcción original para levantar talleres dentro de la fortaleza.
El 2 de julio de 1915 el primer jefe del Ejército Constitucionalista, Venustiano Carranza, decretó que San Juan de Ulúa dejara de ser presidio. Parte del edificio se destinó a residencia eventual del Poder Ejecutivo de la Unión y otra a reducto militar de una pequeña partida para vigilancia. Actualmente es un monumento histórico declarado así desde 1962 por decreto del presidente Adolfo López Mateos y entregado al INAH para su resguardo.
