Gazteluberri va ser un poblament tardà, probablement de finals del segle xii, quan els habitants d'Elesa, despoblat situat a 2 km de l'actual emplaçament de Gazteluberri, es van veure obligats a traslladar-se a una nova ubicació per raons defensives. La població es va situar als peus d'un nou castell que s'havia construït per a defensar la frontera oriental de Navarra. Aquest castell va ser el qual va batejar a la localitat com Castillo-Nuevo. En el segle xvi quan Navarra va ser conquistada per Ferran el Catòlic, aquest va ordenar derrocar els castells fronterers de Navarra i entre ells el de Gazteluberri, pel que actualment no queda rastre algun del castell que va donar nom al poble. El nom del poble s'ha solgut transcriure com Castillonuevo, Castillo Nuevo o Castillo-Nuevo; sent la primera forma la més habitual i l'última la qual és oficial. Els roncalesos anomenaven antigament al poble Gaztuluberri en basc, nom que significa en el dialecte roncalès d'aquest idioma precisament castell nou. L'Euskaltzaindia va establir que el nom de la població en basc és Gazteluberri, similar al nom tradicional, però en euskera batua. Encara que les veïnes valls de Roncal i Salazar són històricament bascòfones i pertanyen a la Zona Lingüística Mixta de Navarra, la veritat és que el poble es troba en una zona romanizada des de fa antic.
