Luzaide/Valcarlos és una població que té una doble tradició en el seu nom, una romanç i una altra de basca, que són completament diferents. Històricament solament el nom romanç, Valcarlos, ha estat oficial, i el nom basc ha quedat relegat a àmbits no oficials. No obstant això, des del 31 de gener de 1989 ambdós topònims van passar a ser cooficials. El nom romanç del municipi, Valcarlos, s'ha associat tradicionalment a la figura de Carlemany, a la Cançó de Rotllà i la mítica batalla de Roncesvalls. El pelegrí francès Aymeric Picaud que va travessar aquestes terres en el segle xii va deixar escrit el següent sobre Valcarlos en el Codex Calixtinus:
«
Al costat d'aquesta aforesta, cap al nord, hi ha una vall que es diu Valcarlos, en el qual va acampar el mateix Carlemany amb els seus exèrcits quan els guerrers van ser morts a Roncesvalls, i pel qual passen també molts pelegrins que van a Sant Jaume de Galícia aforesta.
»
El nom basc de la localitat, Luzaide, significa probablement camí llarg, de luzea (llarg) i bide (camí). El filòleg basc Jean-Baptiste Orpustan opina que el topònim fa referència al llarg trajecte que es veien obligats a realitzar els pastors navarresos amb els seus ramats quan travessaven la vall, abans que s'hi establís un nucli de població estable. Ambdós topònims, Luzaide i Valcarlos, fan referència al conjunt del municipi. El nucli central rep el nom d'Elizaldea (zona de l'església en basc). El gentilici dels habitants de Valcarlos és luzaidarra, que prové del nom basc de la població.
En temps més propers, sol situar-se en el seu entorn proper el lloc en el qual es va produir la batalla de Roncesvalls, en la qual en l'any 778 la rereguarda de l'exèrcit de Carlemany que tornava després d'una campanya militar al sud dels Pirineus, va ser derrotada pels naturals del país que els van tendir una emboscada. La gesta, va donar origen a la Cançó de Roland i, segons es diu, va acabar donant nom al mateix poble (Vall de Carlos) en llengua romanç.
Valcarlos, per la seva situació, va pertànyer durant un temps a les terres de Ultrapuertos, és a dir, a la part del Regne de Navarra que se situava al nord dels Pirineus, però ja per al segle xv se li vincula a la Vall d'Erro, igual que una part del sud de l'actual Baixa Navarra. És ajuntament des de 1592. El seu emplaçament en la frontera ha fet de Valcarlos protagonista de nombrosos fets bèl·lics, com durant la guerra de la Convenció en 1793, i ha marcat també els límits del propi territori municipal.
