Edificio de planta rectangular, que se levanta sobre un talud rocoso. Tiene dos plantas y está flanqueado por dos torres con almenas, que formaban parte de la muralla de la ciudad. La del lado oriental se habilitó como residencia real en el siglo XIII.

El palacio fue habitado por doña Juana. Posteriormente también ocupó este palacio Carlos II y el infante don Luis durante las guerras con Aragón y más tarde Carlos III. Durante la guerra con Castilla residieron en el castillo Blanca de Navarra con su hijo, el Príncipe de Viana, que ha dado nombre al palacio.

Después de la incorporación del Reino de Navarra a la corona castellana en 1512, el Cardenal Cisneros mantuvo en pie la fortaleza para mantener una guarnición permanente que combatiera cualquier intento de sublevación por parte de los navarros.