En 1512 Fernando el Católico mandó construir una "recia fortaleza" en la colina que dominaba el paso de Behobia. En 1518  estaba ya terminada y gobernada por el alcaide, Gonzalo de la Torre y defendía la frontera castellana de los ataques franco-navarros.

En su origen tuvo planta triangular. Fue diseñado por Diego de Vera, y estuvo formado por tres cortinas de 22 m. de largo y 5 m de grosor; y tres cubos circulares en los ángulos de 21 m. de diámetro.

En 1521, tras el fracasado intento de la recuperación de Navarra, el ejército franco-navarro, al mando del almirante Bonnivent, tomó el castillo.

En 1539, el emperador Carlos V, a su paso para Flandes, visitó el castillo acompañado por el duque de Alba. Cuando todo hacía pensar que Carlos V acabaría por consolidar la construcción del castillo, sorprendentemente mandó al capitán general de la Provincia, don Sancho Martínez de Leiva, que lo derribase para evitar que los navarros se hicieran fuertes en él ante posibles reconquistas del reino. Al poco tiempo, en 1542, la fortaleza quedó desmantelada y volada parcialmente con pólvora. Las ruinas que quedaron dieron lugar a que aquella fortaleza fuera conocida como Castillo viejo (Gaztelu-zar)

 La mayor parte de los sillares resultantes de su desmantelamiento se aplicaron en la mejora de las murallas de Fuenterrabia. A partir de este momento sus ruinas acogieron diversas fortificaciones pasajeras e incluso alguna vivienda. 
 

En la actualidad se conservan dos de los muros en toda su longitud. Algunas de sus partes alcanzan los 9 m. de altura.