Luego de dejar el río de la Plata la expedición continuo hacia el sur explorando cada bahía a su paso y siempre hacia el sur, tratando de encontrar ese paso al otro Océano, pero no había suerte y el clima cada vez era más riguroso y frío. Esto llevó a Magallanes a decidir parar durante un tiempo para dejar que pasase el invierno.
El 31 de marzo de 1520 encontraron una bahía resguardada a la que llamaron Puerto de San Julián, actual territorio de Santa Cruz y se dispusieron a invernar durante 6 meses hasta que las temperaturas subiesen de nuevo.
Allí conocieron a los indios que llamaron patagones, por su talla y el tamaño de sus pies envueltos en pieles, al poco tiempo de estar en el lugar se produjo una sublevación, a causa del frío y la convicción que tenían varios capitanes de que la expedición iba mal encaminada.
El deseo de regresar en lo que se consideraba un fracaso por no haber hallado el paso hacia las Molucas, unido a lo inhóspito del paraje , las condiciones de navegación y algunos españoles, molestos porque Magallanes era portugués provocaron descontento entre la tripulación.
Se sublevaron el primero de abril (domingo de Ramos) , apenas fondearon en el puerto de San Julián, cuando los capitanes de las otras cuatro naves tramaron un motín para matar al comandante en jefe. Los conspiradores eran: Juan de Cartagena, veedor; Luis de Mendoza, tesorero; Antonio de Coca, contador; Gaspar de Quesada, capitán de la Concepción. Mendoza, Cartagena y Quesada, se adueñaron de tres naves y dieron el mando de la San Antonio a Sebastián Elcano.
La rebelión fue sofocada el día 7, entonces , Magallanes mandó degollar y descuartizar a Quesada y abandonó en la costa a Juan de Cartagena y al clérigo Sánchez de la Reina. Elcano fue perdonado. Espinosa mató a Mendoza en forma sorpresiva. Fue en esa ocasión cuando Magallanes pronunció las palabras citadas por López de Gomara, que «le sería muy grande vergüenza tornarse de allí, por aquel poco trabajo de hambre y frío, sin llegar al paso buscado, pues cerca de allí había llegado Américo Vespucio y sino hallasen lo que tanto buscaban se volvería».
Pigafetta también registró en el relato del viaje: Nuestro capitán llamó a este pueblo Patagones pero en la crónica no se dan detalles sobre las razones del nombre, con lo cual desde la época de Pigafetta se ha supuesto de que la palabra "Patagonia" se interpreta como "Tierra de los patagones". Los exploradores quedaron asombrados por las huellas de los pies de los Tehuelches, las que artificialmente eran ampliadas por las pieles que les servían de calzado, pies que de todos modos eran mucho más grandes que los de los europeos de entonces (para el siglo XVI la talla media de los europeos era mucho más baja que la actual, mientras que los patagones llegaban a medir 2 m los varones tenían una talla promedio superior a 2 m
La expedición volvió a zarpar el 21 de agosto de 1520 del puerto de San Julián, sin que nada se haya sabido después de ellos. Magallanes dispuso seguir costeando hasta 75° de latitud sur y, si no hallaban el estrecho, ir a las Molucas por el sur de África.
Al poco tiempo la nao Santiago, al mando de Juan Serrano, naufraga mientras exploraba la costa meridional de la Patagonia. Magallanes nombra a Serrano capitán de la Concepción y a Duarte Barbosa capitán de la Victoria.
El 21 de octubre llegó Magallanes al cabo de las Vírgenes y observando una embocadura, ordenó a las naves San Antonio y Concepción que la recorrieran. No vieron fondo y, en una nueva exploración, la San Antonio recorrió cincuenta leguas, por lo que no quedaron dudas de que se trataba de un estrecho. Dada la escasez de víveres, y en consejo de capitanes y pilotos, Esteban Gómez decidió volver a España.