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