After about two and a half years in Mexico City, Esteban left with Friar Marcos de Niza to find the way to rumored rich Indian cities to the north, which Spaniards would come to call the Seven Cities of Cíbola. The viceroy of New Spain (Mexico) sent Esteban along as guide and interpreter because the Indians of northwest Mexico knew and liked him. No armed Spaniards accompanied the friar's expedition because the bishop of Mexico City had convinced the viceroy that there should be a peaceful attempt to find Cíbola.
Marcos and Esteban started northward in March 1539 with hundreds of Indians promised freedom from warfare and slavery if they would cooperate. After a month, at a Mexican Indian village called Vacapa, Marcos sent Esteban ahead with a group of Mexican Indians, telling Esteban to travel about 130 to 150 miles ahead and send back reports and Marcos would follow.
No European ever saw Esteban again. For a month or more he and his Mexican Indians went ahead, traveling through the rest of northern Mexico. Esteban became the first non-Indian to enter the prssent states of Arizona and New Mexico. Through his entire journey, Esteban made arrangements for Indians along the way through the wilderness to feed and shelter Marcos as he arrived.
In early May 1539 Esteban arrived at the Zuni village of Hawikku in New Mexico near today's border with Arizonad, at least 150 miles or more ahead of Friar Marcos. Everything known about his trip and encounter with the Zunis is based on reports the Indians with him gave to Marcos later. The Indians told Marcos that they assumed the Zunis killed Esteban, although they admitted they never saw that happen. In any case, at that point Esteban disappeared from the historical record.
To reach Hawikku from the earlier starting point in Mexico City, Esteban would have walked more than 1,500 miles on this second journey.