La población toma el nombre del castillo bajo el que se construyó, que al ser de edificación tardía respecto a los otros castillos de su entorno, recibió en romance navarro el nombre de Castelnuevo (1280) o Castiel nuevo (1281), que posteriormente evolucionaría hacia Castieyllo Nueuo (1366). El nombre de la edificación terminó por dar nombre al núcleo de población, quedando así incluso tras la destrucción del castillo en el siglo XVI. Con la sustitución del romance navarro por el castellano, el nombre se adaptó fonéticamente a la forma actual: Castillonuevo (1534). En ocasiones aparece ortografiado como Castillo Nuevo o Castillo-Nuevo, aunque se trata de formas poco habituales.^[9]​

La localidad se encuentra en una zona romanceada hacia finales de la Edad Media, contrariamente a la mayor parte del Pirineo navarro, por lo que no queda constancia del nombre que usaron sus habitantes vascoparlantes. Sus vecinos del valle del Roncal, cuyo dialecto nativo, el roncalés, sobrevivió hasta finales del siglo XX, lo llamaban aún por aquel entonces Gaztuluberri. Se trata de una construcción análoga a la romance, compuesta por gaztulu (castillo) y berri (nuevo). La Real Academia de la Lengua Vasca estableció que el nombre de la población en lengua vasca estándar es Gazteluberri, similar al nombre tradicional, pero en euskera batua, como ocurre en casos similares como Carcastillo.^[2]​

Al constituirse oficialmente en municipio, el pueblo lo hizo bajo el nombre que venía usando tradicionalmente en castellano, Castillonuevo, aunque posteriormente siempre aparece como Castillo-Nuevo en los registros de población. En 2014 el municipio recuperó de manera oficial la escritura tradicional en castellano, Castillonuevo, que había seguido usándose extraoficialmente. Desde el 19 de marzo de 2025, por petición del ayuntamiento y tras aprobación por parte del Gobierno de Navarra, se incluye la versión vasca en el nombre oficial, que pasa a ser bilingüe: Castillonuevo / Gazteluberri.^[10]​^[11]​^[1]​

El escudo de armas del lugar de Castillonuevo tiene el siguiente blasón:

Trae de azur y un ciervo de plata sobre base de sínople. Por timbre un yelmo empenachado..

Este escudo aparece en una labra de la fachada de la casa consistorial y está pintado en las vidrieras del Palacio de Navarra.^[12]​

Castillonuevo fue un poblamiento medieval tardío, probablemente de finales del siglo XII, cuando los habitantes de Elesa, despoblado situado a 2 km del actual emplazamiento, se vieron obligados a trasladarse a esta nueva ubicación por razones defensivas. La población se situó a los pies de un nuevo castillo que se había construido para defender la frontera oriental del Reino de Navarra.

En el siglo XVI cuando Navarra fue conquistada por Fernando el Católico, este ordenó derribar los castillos fronterizos de Navarra y entre ellos el de Castillo-Nuevo, por lo que actualmente no queda rastro alguno del castillo que dio nombre al pueblo.^[13]​

Como lo indica el nombre del pueblo, hubo en época medieval un castillo con su torre fortificada. La situación geográfica de la localidad la convirtió durante siglos en estratégica como punto de defensa ante la vecina Aragón y como punto de entrada a los valles de Roncal y Salazar, así como al Almiradío de Navascués.

Desde el siglo XIII hasta finales de la Edad Media se tienen constancia de alcaides. Así, hacia 1280 era alcaide Arnalt Guillén, señor de Agramont. En 1300 se tiene noticia de que se trabajó tanto en la torre como en el muro exterior. En 1319 se realizaron nuevas obras, en la torre, en las garitas, y en las casas. Desde entonces, y hasta 1328, el alcaide Iñigo Ruiz de Aibar percibía una retenencia de 8 libras y 40 cahíces. En 1355, Carlos II elige a Rodrigo de Aibar. La asignación era de 6 libras y 30 cahíces. En 1360 el carpintero Sancho de Beorieta deja constancia de obras de reparación. En 1362, el castillo tenía una guarnición de diez peones ballesteros.

Tras la conquista de Navarra por Fernando el Católico, la fortaleza, como otras, también fue derribada.^[13]​

La parroquia de San Martín está en la parte alta del pueblo. Todavía existen los muros medievales, aunque sufrió obras en el siglo XVI y durante el Barroco.

En el interior conserva un retablo rococó de la segunda mitad siglo XVIII, donde se distinguen cuatro grupos escultóricos. Uno de ellos representa la famosa escena del santo partiendo la capa. De las mismas fechas y similar estilo son otros dos grupos representan Pentecostés y la Crucifixión respectivamente.

Existe también un retablo barroco con imágenes de la época y la escultura gótica de la Virgen de las Victorias procedente de una antigua ermita bajo la misma advocación.^[13]​

De entre las que hay constancia que hubo, San Andrés, Santa Juliana, Santa Victoria y San Facundo, las tres primeras ya están desaparecidas aunque se conserva la toponimia. En la última figura la fecha de 1885 sobre la puerta. Además hay noticia de que en 1711, por Pentecostés, se hacía romería a Sabaquente, hoy día desconocido.^[14]​

Por otra parte, dentro del término municipal, hacia la parte de la sierra de Leire-Illón, está localizado el dolmen llamado del Pasomuerto. Según describen, conserva un túmulo circular de piedras centrales donde no se aprecian losas de cámara. Está enclavado en una zona megalítica donde, igualmente, se encuentran otros vestigios en los adyacentes términos municipales de Navascués y Bigüézal (Romanzado), y es conocida como Estación dolménica de Leire-Illón que hacia 1952^[15]​ ya estudiara Juan Maluquer de Motes.^[16]​

La localidad de Castillonuevo está situada en la parte centro-oriental de la Comunidad Foral de Navarra, a una altitud de 777 m s. n. m. Su término municipal tiene una superficie de 26,34 km² y limita al norte con Navascués, al este con Salvatierra de Esca y Sigüés ambos en la provincia de Zaragoza y la comunidad autónoma de Aragón, al sur con los de Escó y Tiermas también de la provincia de Zaragoza y al oeste con Bigüézal y con el de Romanzado.^[13]​

Dentro del término municipal, cuyo dibujo de los límites asemeja un cuadrado, el casco urbano se sitúa en la parte más nororiental del mismo. Se ubica solamente a 1 km de la frontera con la provincia de Zaragoza, Aragón.

Cuenta con una población de 15 habitantes (INE 2024).

Gráfica de evolución demográfica de Castillo Nuevo[17]​ entre 1842 y 2021

Población de derecho según los censos de población del INE     Población de hecho según los censos de población del INEEn este censo se denominaba Castillonuevo: 1842[18]​

Primer fin de semana de agosto.

• Navarra
• Lista de municipios de Navarra

•   Wikimedia Commons alberga una categoría multimedia sobre Castillonuevo.
• Datos de Castillonuevo - Gobierno de Navarra - Información y datos de entidades locales de navarra.
• Castillo-Nuevo en Bernardo Estornés Lasa - Auñamendi Encyclopedia (Euskomedia Fundazioa)