Transcurridos algunos días, cinco individuos de la flota fueron a la ciudad a comprar brea, y contra lo que pudiera esperarse a continuación de tantos festines, no se los dejó volver, por lo que el resto de nuestra gente combatió y apresó una canoa, en la que iba un hijo del rey de Luzón con cinco mujeres, un niño de dos meses y cinco hombres. El general los puso en libertad mediante rehenes para que el príncipe luzonés procurase hasta lograrla la devolución de los castellanos.
No fueron reintegrados mas que dos, y como habían huído de la Victoria otros dos, fueron cinco las bajas sufridas en Borneo por los expedicionarios.
Estos salen de allí el 5 de agosto, y el 15 cae en su poder una canoa, en la que había 30.000 cocos. Luego están treinta y siete días reparando los buques.
Antes de hacerse a la mar destituyen al capitán mayor, y, por unanimidad, eligen para substituírle a Gonzalo Gómez de Espinosa, y por capitán de la Victoria, a Juan Sebastián Elcano. La remoción de Caraballo obedeció a las antipatías que se había conquistado, pues no se sujetaba a las cédulas reales ni atendía los consejos de nadie, reconociendo como única ley su capricho.
Tras una navegación muy rica en incidentes y trabajos, llegó la pequeña armada el 8 de noviembre a una de las islas Molucas, a la de Tidor, cuyo rey fué el día 9 a darles la bienvenida a nuestros compatriotas. «Ahora se cumplen—les dijo—dos años que yo conocí por el curso de las estrellas que vosotros érades enviados de un gran rey a buscar esta nuestra tierra, por la cual cosa vuestra venida me ha seydo más cara e graçiosa, pues que por las estrellas tanto tiempo antes me fué anunçiada. E çabiendo que no acaesçe jamás alguna cosa destas sin que primero no sea de la voluntad de los dioses o de las estrellas ordenado, no seré tal con vosotros que quiera contrastar la voluntad de los cielos, sino, con buen ánimo y voluntad, de aquí adelante, dexando aparte el nombre real, pensaré que soy como un gobernador de aquesta isla en nombre de vuestro rey.»
Almanzor, que así se llamaba aquel monarca, iba descalzo, y su indumentaria consistía en una camisa labrada de oro, un pañuelo blanco ceñido hasta el suelo y un velo de seda en forma de mitra. Al entrar en la capitanía se tapó las narices para evitar, como musulmán que era, el olor del tocino. Los castellanos le regalaron una silla de terciopelo carmesí, una ropa de terciopelo amarillo, un sayón de tela falsa de oro, cuatro varas de escarlata, un pedazo de damasco, otro de lienzo, un paño de manos labrado de seda y oro, dos copas y seis sartales de vidrio, tres espejos, doce cuchillos, seis tijeras y seis peines.
Almanzor les autorizó para matar a quienes les molestasen, y hombre de curiosidad voracísima, examinó el estandarte imperial, un retrato de Carlos V, la moneda y un peso.
Muy pronto se cambiaron entre él y Gonzalo Gómez de Espinosa juramentos de paz y contratación. Aquel sería amigo de España y le facilitaría especias por paños, lienzos y sedas.
En diciembre reconocieron la soberanía del emperador, Corala, señor de Terrenate, Luzuf, rey de Gilolo, y los de Maquián y Bachián. Eran muy afamados por su lujuria y por su prole. Corala tenía cuatrocientas mujeres «gentiles en ley y en persona» y cien jorobadas para que las sirvieran de pajes. De Luzuf se cuenta que era padre de seiscientos hijos. Veintiséis tenía Almanzor, y doscientas mujeres. «En cenando—dice Gomara—mandaba ir a la cama a la que quería... Era celosísimo, o lo hacía por mor de los españoles, que luego miran y sospiran, y hacen del enamorado.»
El rey de Tidor les encareció a los castellanos que le suplicasen de su parte a Carlos V el envío de muchas fuerzas, para vengarse del cacique de Burú, que había muerto a su padre y arrojado su cadáver al mar, y para que enseñasen a los tidoreses nuestra religión y nuestras costumbres, y les dió para el emperador papagayos rojos y blancos, miel y varios indios.