Celebradas sus bodas y despachados favorablemente sus asuntos en la Corte, se ocup� el adelantado de ultimar los aprestos de su viaje. No siendo suficientes sus recursos pecuniarios, tuvo que acudir a varias personas que le proporcionaron los fondos necesarios para la compra y aprovisionamiento de las naves, armas, p�lvora, municiones, algunas piezas de artiller�a, clavaz�n, provisiones, etc., que se oblig� a pagar en Guatemala o a su desembarco en Puerto Caballos.
Compon�an la armada la nave Santa Catalina, de que era capit�n y maestre Domingo de Alvarado, y los galeones Santa Mar�a de Guadalupe y Trinidad.
El reclutamiento de la gente de guerra para la expedici�n estaba terminado a fines de 1538. La �ltima licencia para embarcarse "en las naos del Adelantado don Pedro de Alvarado" aparece en el registro de pasajeros con fecha 24 de diciembre.
El 5 de octubre obtuvo licencia para embarcarse en la armada, con t�tulo de Escribano de Indias, Baltasar de Montoya, vecino de Burgos, hijo del doctor de Castillo Montoya y de Menc�a Parda. El escribano Montoya, sin sospecharlo siquiera, era el hombre que iba a decidir la suerte del conquistador de M�xico y Guatemala.
Tambi�n obtuvo licencia para embarcarse el bachiller Juan Alonso, cl�rigo presb�tero de la Orden de Santiago de la Espada, que iba de capell�n y confesor del adelantado "para administrar los sacramentos".
Do�a Beatriz se hizo acompa�ar de un lucido grupo de damas j�venes de nobles familias y de la gente de servicio que crey� necesaria. El Cat�logo de pasajeros a Indias enumera entre las damas de do�a Beatriz a do�a Mar�a de Horozco, do�a Isabel de Anaya, do�a Francisca de San Mart�n, do�a Ana, do�a Luisa, do�a Ana Fadrique, do�a Mar�a de Caba, do�a Juana (�de Arteaga?) y do�a Ana Mej�a.
Las naves del adelantado se hicieron a la vela en el puerto de Sanl�car de Barrameda a principios de 1539. Navegando con viento favorable llegaron a poco a la Isla Azores, escala acostumbrada en los viajes al Nuevo Mundo.
A principios de marzo surgi� la armada en el puerto de Santo Domingo, de la Isla Espa�ola, a donde lleg� "en salvamento" seg�n se expresa Alvarado en su informe al rey. Da tambi�n noticia de su llegada a la isla el historiador Gonzalo Fern�ndez de Oviedo, con quien el adelantado tuvo varias conversaciones mientras descansaba la gente y se renovaban las provisiones de las naves.
Terminado el descanso en la Isla Espa�ola, el adelantado sali� el 20 de marzo con destino a la provincia de Honduras. Dos semanas m�s tarde, el viernes Santo de 1539, 4 de abril, fondearon las naves en Puerto Caballos. El lugar estaba desierto.
Los tripulantes desembarcaron y procedieron a construir abrigos de fortuna para las personas y para el cargamento. Alvarado refiere en su carta a Carlos V que, despu�s de haber desembarcado encontr� un hombre perdido quien le inform� que hac�a d�as andaba extraviado por los montes buscando camino para ir a la villa de San Pedro y sin poder dar con �l. Este episodio da idea del estado de abandono y despoblaci�n en que se hallaba la provincia de Honduras en 1539.
El primer cuidado de Alvarado, una vez en tierra, fue enviar aviso de su llegada al cabildo de Guatemala y pedirle que reunieran a sus indios y se los enviaran para conducir su cargamento. Con este fin, el propio d�a de su arribo escribi� al cabildo la carta que dice:
Magnificos Se�ores: Ya creo que por cartas m�as, que yo escrib� a esa Ciudad, de Valladolid, sabr�is mi venida, y el suceso de mi buen despacho. Agora no habr� de nuevo que decir, sino que, gracias a Ntro. Sr., yo soy llegado a salvamento a este Puerto de Caballos, con tres naos gruesas y trescientos arcabuceros y otra mucha gente, donde pienso detenerme algunos d�as, hasta que desa Ciudad me venga despacho y ayuda para mi pasage. P�doos, Se�ores, por merced, que en todo se favorezca a esos espa�oles que env�o para que m�s cumplidamente yo sea prove�do de lo necesario para mi partida. Porque yo env�o a mandar a Paz, que luego se junten todos los m�s indios que fuere posible de los m�os; y as� recibir� merced con los dem�s que fuera destos se me enviaren; porque dem�s de recibir yo merced en ellos, S.M. lo manda. Y porque m�s particularmente vuestras mercedes sabr�is del portador desta todo lo de mi jornada, por no ser largo lo dejo de decir, y porque placiendo a Ntro. Sr. nos veremos presto. Solamente me queda de decir como vengo casado, y do�a Beatriz est� muy buena: trae veinte doncellas muy gentiles mujeres, hijas de Caballeros, y de muy buenos linages; bien creo que es mercader�a, que no me quedar� en la tienda nada, pag�ndomela bien, que de otra manera excusado es hablar en ello. Ntro. Sr. guarde sus magnif�cas personas como V. mercedes deseais. De Puerto Caballos a 4 de abril de 1539. A servicio de Vuesas mercedes.El Adelantado Alvarado.
Al d�a siguiente de su desembarco, Alvarado comenz� a abrir camino para el interior con doscientos "hombres cristianos" provistos de azadones, machetes y hachas para derribar los altos �rboles de la costa. Trabajando activamente, en diez d�as abri� un camino bien ancho hasta la villa de San Pedro, por el cual pod�an pasar dos recuas de mulas en opuestas direcciones. Desde San Pedro notific� su llegada a las autoridades de Honduras, establecidas en la ciudad de Gracias, y volvi�ndose al Puerto de Caballos emple� veinticinco d�as en descargar sus naves con ayuda de su gente, sin perder un solo hombre, si bien muchos enfermaron por el rigor del clima, pero fueron atendidos y curados.
La tregua de que hab�an disfrutado los naturales de Guatemala bajo el gobierno de Maldonado hab�a cesado desde el regreso del cruel conquistador, que volv�a m�s seguro que nunca de sus poderes y facultades sobre los habitantes indefensos. El historiador Remesal no exagera cuando dice que "con esta venida del adelantado se inquiet� y alter� toda la tierra y los miserables naturales ped�an a los montes que cayesen sobre ellos y los cubriesen, y a la tierra que los recogiese en sus entra�as: para escaparse de la furia del adelantado que los amenazaba".
Raz�n ten�an los indios desventurados para temer los vej�menes de Alvarado a su regreso de Espa�a. El camino de Puerto Caballos a Guatemala volvi� a ser la v�a dolorosa de los infelices naturales, en cuyos lomos hizo transportar el adelantado no s�lo sus equipajes y objetos de casa, sino las anclas, jarcias, la clavaz�n, el velamen y la artiller�a que destinaba a la flota que estaba construyendo en Iztapa para emprender la expedici�n a las Indias Orientales.
El autor del Memorial de Solol� fue testigo de alguna de las violencias de Alvarado a su regreso a la provincia de Honduras. El pueblo de Solol�, tambi�n llamado de Tecp�n-Atitl�n, era de la encomienda del adelantado, y sus hombres aptos, obedeciendo sus �rdenes, marcharon a servirle a Puerto Caballos. Entre ellos se encontraba Francisco Hern�ndez Arana, autor del Memorial, quien dice acerca de este viaje: "Antes que terminara el segundo a�o del tercer ciclo, fueron a recibir al Se�or Tunatiuh a Porto Cavayo, cuando desembarc� Tunatiuh despu�s de haber ido a Castilla. Uno de los Se�ores fue a recibirlo. Nosotros tambi�n fuimos all� �Oh, hijos m�os! Entonces hirieron al Ahtzib Caok por cosas de su parcialidad [el 30 de abril de 1539]".