Partieron el 24 de agosto de 1535 del puerto de San Lúcar de Barrameda siendo una de las mas grandes expediciones realizadas hasta el momento, estaba compuesta de once naves y unos 1300 personas en dirección a las islas Canarias. En ella viajaban hidalgos, caballeros de órdenes, capitanes experimentados, parientes y allegados del Adelantado, regidores, contadores, escribanos, tesoreros, veedores, etc. Llegaron en los primeros días de enero de 1536 al estuario en donde poco después, en febrero, se fundó Santa María del Buen Aire, en su margen occidental. Esta iba a ser la base principal para explorar el camino que llevaría hasta la Sierra de la Plata.
La expedición era una de las mayores que habían salido de España. La integraban trece naves equipadas en España, a las que se agregaron otras tres en las Canarias, adquiridas mediante contrato de Pedro de Mendoza con Pedro Fernández de Luro.
Se incorporaron a la gran aventura hombres conocidos como guerreros experimentados: Pero Hernández de Ludueria, maestre de campo de la gente de a caballo; Juan Osorio, maestre de campo de la infantería; Juan Ayolas, alguacil mayor de infantería; Gaspar Gómez, sargento mayor de infantería; Gonzalo de Cuadros, capitán de mar; Juan de Salazar, capitán del navío El Anunciador. Formaban parte de la expedición, también, Domingo Martínez de Ira-la, Rodrigo de Cepeda, hermano de santa Teresa de Ávila; el hermano del adelantado, Diego de Mendoza; el alemán Ulrich Schmidl, etc. En total unos 1.500 a 1.800 hombres.
La armada partió de Sanlúcar de Barrameda el 24 de agosto de 1535. Durante la travesía, la carabela Durañona se desvió de la ruta y llegó al puerto de Santo Domingo; otra nave naufragó en la costa del Brasil. Por tanto, sólo llegaron al río de la Plata 14 naves de diverso porte.
En las Canarias se produjeron sucesos que habrían de tener mucha repercusión, probablemente hasta en los desastres de la expedición. Entre Juan Ayolas y Juan Osorio
se produjo un distanciamiento inamistoso a causa de la actividad diversa que asumían ante ciertas extralimitaciones de los soldados; Osorio era valiente y se le temía, pero con los soldados era un buen compañero y amigo. Ayolas, Galaz de Medrano, Juan de Cáceres denunciaron a Mendoza expresiones hostiles de Osorio, y el adelantado, postrado en cama a causa de la enfermedad que sufría, falló que Osorio fuese tomado dondequiera que se hallase y muerto a puñaladas o estocadas o en cualquier forma, hasta que el alma le saliese del cuerpo. Tales eran los hábitos de los hombres de guerra de entonces; si no tenían mayor ponderación al exponer la propia vida, tampoco sentían respeto por la vida ajena.
Cuatro de las naves de la armada entraron en la bahía de Río de Janeiro el 30 de noviembre y el resto siguió rumbo al río de la Plata al mando de Diego de Mendoza.
El 3 de diciembre se preparó la ejecución de Osorio; Ayolas y Galaz de Medrano lo tomaron de improviso de los brazos y lo mataron a puñaladas. El cadáver fue abandonado en la playa con un letrero que decía: "A éste mandó matar don Pedro de Mendoza por traidor y amotinado". Se hizo luego una información por Ayolas mismo como para reunir testimonios de los soldados y justificar el hecho cumplido. El padre del muerto inició juicio para salvar el buen nombre de su hijo y a los 19 arios la sentencia declaró que Mendoza se había excedido en sus poderes y en su severidad.