Acompañó a Francisco Vázquez de Coronado en la expedición que éste emprendió al norte de México en busca de Cíbola y las siete ciudades de oro. Al inicio del viaje tuvo el grado de capitán de caballería (maestre de campo) y al final de la expedición fue ascendido a Teniente General. La expedición partió de la población de Compostela (Nayarit) y en la población de Culiacán (Sinaloa) fue dividida en dos, la más lenta viajaba con indios a pie, ganado y abastecimientos, en tanto la otra, más ligera, viajaba a caballo. Tristán de Luna fue nombrado segundo al mando de la avanzada, que dirigía Vázquez de Coronado. La expedición atravesó el hoy estado de Sonora (México), tomó los pueblos de los zuñi en julio de 1540 y marchó a Tiguex (Nuevo México), en donde levantaron campamento en espera del resto de la expedición. De allí partieron en busca de las míticas ciudades de Cíbola y Quivira: durante treinta y siete días exploraron la región hasta que Vázquez de Coronado decidió regresar para reunirse con el resto de la expedición. Los dos grupos se encontraron y pasaron el invierno en Tiguex, cerca de la ciudad de Santa Fe (Nuevo México), a orillas del Río Grande (Río Bravo). La expedición terminó en fracaso.

En 1545 contrajo matrimonio con Isabel de Rojas, viuda de Juan Velázquez y Francisco Maldonado y heredera de sus fortunas, con la que tendría dos hijos, y tres años después, en 1548, fue enviado a Oaxaca para sofocar un levantamiento de nativos. En 1557 el virrey Luis de Velasco le encarga una expedición a Santa Elena, en la actualidad Tybee (Georgia), en la costa atlántica de los actuales Estados Unidos para establecer un puesto avanzado. Partió hacia el destino con el título de gobernador de la Florida, al mando de 500 soldados y 1.000 colonos. En agosto de 1559 llegó a la bahía de Pensacola, donde fundó la ciudad de Santa María, que fue al poco destruida por un huracán. Desorientado y sin poder encontrar el camino de Santa Elena, envió un navío, que naufragó en una tormenta. Relevado del cargo, se le ordenó ir a España a dar cuenta de sus actos y fue destituido del cargo. Inválido tras la expedición a la Florida, regresó a América y murió en Ciudad de México en 1573.