La formule « Nouvelle Espagne » apparaît sous la plume d'Hernán Cortés dans une lettre qu'il adresse à Charles Quint au cours de son expédition au Mexique, qui aboutit à la prise de Mexico en août 1521 et à l'effondrement de l'Empire aztèque. La vice-royauté de Nouvelle-Espagne est officiellement créée en 1535.
La liste des vice-rois de Nouvelle-Espagne est donc précédée de la liste des vice-rois des Indes (occidentales), qui commence avec Christophe Colomb en 1492, des principaux gouverneurs des possessions espagnoles dans les Caraïbes, quand ils ne sont pas vice-rois, et des gouverneurs de la Nouvelle-Espagne avant la création de la vice-royauté.
Vice-rois et gouverneurs des « Indes »
En 1492, Christophe Colomb croit avoir atteint les Indes, c'est-à-dire l'Asie, et devient donc vice-roi des Indes, en vertu des capitulations de Santa Fe ; par la suite, les Indes d'Amérique sont redéfinies comme « Indes occidentales », par opposition aux Indes d'Asie, les Indes orientales.
De fait, jusqu'en 1509, la seule colonie espagnole est l'île d'Hispaniola ; en 1509 a lieu la conquête de la Jamaïque et en 1511, celle de Cuba, qui supplante Hispaniola comme principale colonie.
En 1519, le gouverneur de Cuba, Diego Velasquez, envoie Hernan Cortés dans une mission d'exploration du Mexique, qui se transforme en expédition de conquête, contre l'avis de Velasquez, qui considère Cortés comme un rebelle ; mais le conquistador réussit à obtenir l'accord de Charles Quint à son opération.