La República de Venecia, potencia muy presente en el Mediterraneo centro-oriental desde el siglo XI, emprendió en 1711 la construcción de la fortaleza para completar el sistema defensivo de Nauplia y hacer frente a la amenaza turca.

Se erigió sobre un monte que dominaba la ciudad y la antigua fortaleza de Acronauplia. Las obras, realizadas según los planos de los ingenieros franceses Lasalle y Levasseur, se prolongaron hasta 1714. El nombre de la fortaleza hace referencia a Palamedes, héroe de la guerra de Troya e hijo de Nauplio, que dio nombre a la ciudad.

En 1715 la nueva fortificación veneciana fue puesta a prueba por las fuerzas turcas de Silahdar Damat Alí pachá,^[1]​ que tomaron la ciudadela en solo siete días y masacraron a la guarnición.^[2]​

En la noche del 28 al 29 de noviembre de 1822, la ciudadela fue reconquistada por los patriotas griegos de Stáikos Staïkópoulos.

El resto del siglo XIX y hasta principios del XX, la fortaleza sirvió como cuartel y prisión.

Se construyó sobre un peñasco de 216 mts de altura que domina Nauplia,^[3]​ ciudad situada en lo más profundo del golfo de Argos. La fortaleza está formada por ocho bastiones conectados entre sí por murallas. Los bastiones fueron bautizados por los venecianos con los nombres de las provincias venecianas, y posteriormente fueron renombrados por los turcos. Finalmente, los griegos, tras la reconquista de la ciudadela, les dieron los nombres actuales. Estos nombres recuerdan a generales de la Antigua Grecia o de la mitología (en el caso de Aquiles), a excepción de los dos bastiones situados al noroeste.

• Bastión Epaminondas: controla el acceso a la fortaleza por la entrada principal[2]. Este bastión no estaba terminado cuando los turcos tomaron la ciudadela en 1715 y completaron su construcción según los planos de los ingenieros venecianos. En el exterior de la puerta, colocaron un relieve que representa un turbante, una espada y una maza.
• Bastión Milcíades;
• Bastión Leónidas;
• Bastión Foción; está situado en el extremo sur.
• Bastión Aquiles;
• Bastión Temístocles;
• Bastión Agios Andreas (San Andrés); debe su nombre a la capilla que se encuentra en él.
• Bastión Robert, situado en el extremo noroeste, sobre la ciudad, debajo del bastión Agios Andreas. Debe su nombre a un oficial francés filohelénico, el teniente Robert, compañero de Charles Nicolas Fabvier, que murió en diciembre de 1826 cuando Fabvier y su tropa se unieron a los defensores de la Acrópolis de Atenas sitiada por los turcos.

Una escalera de más de 900 peldaños permite subir a pie a la ciudadela desde Nauplia.

•  
  Monte-Palamida nuovamente fortificato - Coronelli Vincenzo Maria - 1708
•  
  Bastión «Aquiles» dominando el golfo Argólico.
•  
  Interior de la fortaleza.
•  
  Bastión Temístocles.
•  
  Vista de Nauplia y la Acronauplia.
•  
  Castillo Palamedes en la ciudad de Nauplia