Sandoval llegó con Hernán Cortés a la Nueva España en 1519, siendo el más joven de sus capitanes.
Tras la alianza con Tlaxcala en 1519, le fue entregada en matrimonio la princesa Tolquequetzaltzin de Tizatlán, bautizada como Isabel, con la que tuvo el mismo año un hijo llamado Juan.
Aunque se trataba de un matrimonio indígena, por tanto no vinculante para los cristianos, es aparente que Sandoval no se unió con ninguna otra mujer y Juan fue su único hijo, el cual heredó su encomienda en Nueva España.
Sandoval destruyó la ciudad, y luego volvió a su tarea de transportar los navíos para el ataque sobre Tenochtitlán.
Más tarde Sandoval fue enviado a la región de Coatzacoalcos, pacificando Huatusco, Orizaba, Tuxtepec y Oaxaca.
Luego Sandoval viajó con Cortés a Honduras en 1524, donde fue nombrado alguacil y se le concedieron algunas encomiendas, como Xacona.
Durante el viaje enfermó, falleciendo en 1528 en Niebla al poco tiempo de llegar a España.