После этого опасного инцидента вернувшиеся ветры и течения вынесли флотилию из полосы штиля, и она продолжила переход через Атлантику. Стараясь миновать португальские поселения-фактории на бразильском побережье и выйдя к нему в районе сегодняшнего Ресифи 29 ноября, Магеллан повел каравеллы дальше на юг в бухту Рио-де-Жанейро, где, по свидетельству уже побывавшего в тех краях лоцмана Карвальу, португальцев пока не было. Ранним утром 13 декабря 1519 года утомленные долгим и нелегким переходом через океан парусники вошли в великолепную гавань Рио, которую Магеллан назвал Санта-Люсиа в честь ее дня по католическому календарю, но прежнее звучное название этого места возобладало и дошло до наших дней. Здесь экипажи провели две отдохновенные недели в общении и бойкой торговле с радушными индейцами. Верный себе Пигафетта, охваченный массой экзотических впечатлений, вносит в свой дневник подробные, порой даже пикантные, но не во всем правдивые записи о благоухающей тропической природе этого края, нравах и обычаях его диких обитателей, а также о курьезных эпизодах пребывания в нем путешественников.

Во время пребывания в Рио племянник епископа Фонсеки Антонио Кока, назначенный Магелланом вместо снятого Картахены на пост капитана «Сан-Антонио», проявил: по отношению к главе экспедиции крайнюю нелояльность, выпустив из-под стражи арестованных. Благодаря решительным действиям Эспиносы, этот начинавшийся мятеж по приказу Магеллана был тоже подавлен. На этот раз генерал-капитан заменил арестованного Коку своим родственником Альваро Мескитой, а его вместе с Картахеной почему-то вновь оставил под наблюдением Мендосы на борту «Виктории». Мескита же оказался порядочным человеком, но слабым капитаном, что опасным образом проявилось позднее.

День наступившего Рождества Христова экипажи отмстили уже на борту каравелл, так как на следующий день 26 декабря они покинули чудесную гавань и гостеприимных индейцев, взяв курс на юг в тщательных поисках пролива в Южное море, который, по мнению Магеллана, должен был находиться где-то в этой части нового континента. Такое обследование требовало прочесывания линии побережья, а это означало продвижение на близком расстоянии от него и заходы в каждое его водное углубление. Около 13 января лоцман Карвальу увидел на горизонте три высоких холма, знакомых ему по предыдущему плаванию у этих берегов, которые находятся около сегодняшнего уругвайского курорта Пунта-дель-Эсте. А вскоре по движению вдалеке возникла довольно высокая гора, при виде которой Магеллан громко прокричал «Монте видео», то есть «Вижу гору», что впоследствии стало названием столицы Уругвая Монтевидео, расположившейся затем у горы Лас Анимас.

Сейчас флотилия находилась у входа в огромное устье реки Ла Плата, которую в 1516 году открыл Хуан де Солис, погибший на ее берегу на обеденном костре туземцев. Полагая, что искомый пролив может начинаться где-то в тех водах, Магеллан отправил на их обследование самую легкую из своих каравелл «Сантьяго». После похода, когда вся флотилия стояла на якорях, капитан Серрану доложил, что залив представлял собой соединенные устья нескольких рек или устье одной мощной реки, но не пролив. Желая еще раз подтвердить наблюдения Серрану, Магеллан посылает по одной плоскодонной лодке от каждой каравеллы на более подробное обследование этих вод, но они тоже обнаружили растущую пресность воды по мере продвижения вглубь вдоль их берегов. Убедившись, что здесь пролива не существует, глава экспедиции с еще большей уверенностью стал считать, что он непременно должен быть дальше к югу, и хотел найти его пока еще позволяло южное лето до наступления суровых зимних холодов.

2 февраля нового, 1520 года флотилия снялась с якорной стоянки неподалеку от будущего Монтевидео и направилась на юг. После пересечения просторов устья Ла Платы суда достигли мыса Святой Марии, до которого в свое время дошел Жоау де Лишбоа и где начинались неизведанные земли. Как и раньше, стараясь не пропустить возможного места пролива, Магеллан шел близко от берега, но соблюдая безопасное расстояние. Через одиннадцать дней экспедиция оказалась у бухты Баиа Бланка, где ей пришлось пережить страшный шторм, которая тоже подверглась тщательному, но безуспешному обследованию. Еще 10 дней спустя по пути на юг перед ней возник новый залив шириной около 60 миль с такой глубиной, что экипажи при измерении ее не смогли достать дна.

За полуостровом на его южной стороне была обнаружена очень уютная спокойная гавань, носящая сегодня название Гольфо Нуэво, где флотилия получила несколько дней передышки в своих трудах, а 27 февраля перед ней открылся очередной широкий залив, который был назван Баиа-де-лос-Патос, или Заливом уток. Никаких уток там не было, но вода и побережье кишели массами пингвинов, для которых у европейцев пока не существовало названия, и они называли их утками без крыльев. Там же было множество тюленей, которые вместе с пингвинами стали для путешественников одним из местных источников питания. Здесь начинались огромные холмистые пространства, покрытые в зависимости от сезона сочной зеленой или бурой травой, питавшей огромные стада южной породы лам-гуанако. В этих же землях европейцы обнаружили пум и американского страуса pea. От побережья Атлантического океана эта гигантская по своим размерам территория простирается до восточных склонов Анд, откуда берут свое начало многочисленные реки, пересекающие ее с запада на восток.

Не обнаружив пролива, каравеллы продолжали путь на юго-запад, следуя вдоль берега незнакомой земли в тисках злых и продолжительных штормов, сильно сдерживавших их продвижение, пока в последний день марта они не достигли удобной бухты, названной Магелланом Пуэрто Сан-Хулиан. С каждым днем погода становилась все более холодной, предвещая конец местного лета и наступление месяцев зимы. Глава экспедиции отдал приказ расположиться здесь на стоянку до существенного потепления для продолжения поиска неуловимого залива. Помня о поведении и настроениях ряда своих подчиненных, Магеллан расположил свой флагман в узком проходе в гавань стоянки, а всем остальным каравеллам приказал бросить якоря в ее расширенной внутренней части. Эта предусмотрительность позволяла главе флотилии контролировать выход из залива, и она, как подтвердили последующие события, оказалась чрезвычайно важной.

По записям Антонио Пигафетты, «они оставались там в течение двух месяцев, не встречая никого. Но однажды случилось, что они увидели на берегу гавани огромного как гигант человека, который плясал и пел, посыпая при этом свою голову землей. Капитан тогда послал одного из своих людей к нему делать то же самое как свидетельство мирных намерений. Он это сделал и привез человека к капитану на маленький остров. Когда человек оказался перед капитаном, его охватило огромное удивление, и своим вверх поднятым пальцем он сделал знак, давая понять, что они пришли с неба. А был он такой высокий, что они не доставали даже до его пояса». Так итальянский аристократ-спутник Магеллана запечатлел встречу с первым местным жителем новой земли. Хорошо сложенный гигант был одет в шкуры гуанако, а ноги его были обуты в шкуры, набитые соломой, отчего они казались просто громадными, что и побудило Магеллана назвать его «патагон» от испанского «огромная нога», а его землю соответственно «Патагонией».

Патагонцы вели кочевой образ жизни, перемещаясь следом за стадами гуанако, охота на которых обеспечивала их практически всем необходимым в их суровых условиях. Их главным оружием были короткие луки и примитивные дубинки. Некоторые из них вслед за первым своим соплеменником, получившим щедрое количество европейских безделушек, несколько раз побывали на каравеллах, надеясь приобрести такие же подарки или получить их в обмен на скудные предметы своего охотничьего и рыбачьего промысла. Других индейцев путешественники здесь больше не встречали за все пять с лишним месяцев своего пребывания в этой гавани.