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