The US state of New Mexico, incorporated 1912, naturally kept the same name as its predecessor, New Mexico Territory. That territory, which originally included what later split off as Arizona Territory, received its English name in 1848, when Mexico ceded it to the US. It was a calque of the short form of the Spanish name for the territory, Santa Fe de Nuevo México (Holy Faith of New Mexico).

The Mexican territory of Santa Fe de Nuevo México kept its colonial Spanish name when Mexico declared independence in 1821. The colonial name, Santa Fe de Nuevo Méjico, was established when it was declared a province of New Spain in 1598. Notably, the indigenous Pueblo successfully fought off and expelled the colonists in the Pueblo Revolt of 1680 before they returned in force 12 years later.

Nuevo Méjico is, it turns out, also a calque of the Nahuatl name for the territory, Yancuic Mexico. Aztec folklore describes their undertaking of a massive migration from the north beginning in 1064 or 1065, with one of the starting points being Mexica. By the height of the Aztec empire, Yancuic Mexico was used metaphorically to describe the thriving Pueblo cities to the far north.