El 10 de agosto de 1519 salió la flota de Sevilla, y el 20 de septiembre partió de Sanlúcar de Barrameda, dirigiéndose a las islas Canarias o Afortunadas. Estuvo allí proveyéndose de carne, agua y leña, y el 2 de octubre salió del puerto de Montaña Roja, de la isla de Tenerife, con rumbo al sudoeste; pero el 3 del mismo mes, hallándose en 27° de latitud norte, cambió de itinerario. Juan de Cartagena manifestó su disconformidad con aquella variación de ruta.
Quince días después llegó la armada al paralelo de Sierra Leona. Una noche, hallándose en la costa de Guinea, Cartagena, desde su nave, saludó a Magallanes diciéndole: «Dios os salve, señor capitán e maestre, e buena compañía.» Magallanes le respondió que era llamándole capitán general como tenía que saludarle.
Estando la mar calmosa, el general hizo venir a su navío a los capitanes y pilotos de los demás, y habiéndose promovido muy viva discusión sobre la manera de hacer los saludos, requirió a Cartagena a que se le diera preso; el requerido solicitó, inútilmente, la ayuda de ciertos jefes, que tenía por incondicionales amigos suyos, para prender a Magallanes, y este amarró por los pies, en un cepo, a Cartagena, y si consintió en confiárselo a Luis de Mendoza, fué a condición de que se lo había de entregar cuando se lo reclamara. El cargo que el apresado marino había venido desempeñando se le otorgó al contador Antonio de Coca.
Prosiguiendo el viaje, el 13 de diciembre arribaron a un puerto que fué llamado de Santa Lucía, donde traficaron con los naturales del país. En el Diario o derrotero del viaje de Magallanes, desde el cabo de San Agustín, en el Brasil, hasta el regreso a España de la nao Victoria, escrito por Francisco Albo, se consignan noticias de aquellos indígenas, de las producciones allí más copiosas y de los cambalaches que hicieron los expedicionarios: «Hay buena gente y mucha, y van desnudos, y tratan con anzuelos y espejos y cascabeles por cosas de comer, y hay mucho brasil.»
Magallanes relevó de la jefatura de la San Antonio al contador Coca, la encomendó a Alvaro de Mezquita, sobresaliente de la Trinidad, y el 27 de diciembre reanudó la exploración de la costa.
Hacia mediados de enero de 1520, principiaron a reconocer con minuciosidad el interior del río de la Plata, durando el reconocimiento hasta el 7 de febrero. En el cabo de San Agustín se vió conturbada la flota por un violentísimo temporal. Allí se le acercaron en canoas muchos indígenas. Uno de ellos, vestido con una piel de cabra, entró con asombrosa desenvoltura en la nave de Magallanes. Este le regaló una camisa de lienzo y una camiseta de paño encarnado. El 13 de febrero se encontraron cerca de unos «bajos donde la Victoria dió muchas tocadas», y el 27 en una bahía en la que faltaba toda clase de provisiones. En una isleta próxima a ella cogieron ocho lobos marinos y varios patos.
Magallanes reclamó a Luis de Mendoza la entrega de Juan de Cartagena, y encargó su custodia a Gaspar de Quesada.
El 31 de marzo llegaron al puerto de San Julián.
Al día siguiente, domingo de Ramos, el capitán general llamó a los jefes y pilotos de los otros navíos para que fueran al suyo a oír misa y a comer, y todos acudieron al llamamiento, menos Juan de Cartagena, por hallarse preso, y Gaspar de Quesada, por estarle ordenada su guarda.
El país era muy frío y estéril; los mantenimientos iban escaseando, y Magallanes prescribió la economía en las raciones para que fuesen más duraderas. Por todas estas causas, los expedicionarios, muy descontentos, le pidieron que regresara a España, pero se apresuró a contestarles que él había de cumplir la misión que le había confiado el emperador, y que, en todo caso, preferiría la muerte a un retorno que tenía por ignominioso.