Вот почему он, не теряя драгоценного времени, уже в феврале 1500 года назначает главой новой крупной экспедиции Педро Альвареса Кабраля, который вывел ее из порта Лиссабона 9 марта того же года после торжественной церемонии в присутствии самого короля, министров, знати и высшего духовенства, что должно было продемонстрировать государственную важность данного предприятия. Кабралю было всего тридцать с небольшим лет.
Несмотря на большую значимость его открытия и совершенного им плавания в Индию, о нем и его флотилии до нас дошло совсем немного сведений. Кабраль происходил из древнего аристократического рода в районе города Коимбры, был идальго в совете короля Дона Мануэля и пользовался не только его расположением, но и доверием. Первопроходец пути в Индию, Васко да Гама, тоже высоко ценил достоинства капитана экспедиции и снабдил его очень ценными навигационными и другими инструкциями.
Согласно полученным указаниям, Кабралю предписывалось не заходить на Канары или острова Зеленого Мыса, если у его крупной флотилии из примерно 14 парусников будут оставаться достаточные запасы питьевой воды. Это оказалось возможно благодаря предложению да Гамы хранить воду не в бочонках, как делалось обычно, а по арабскому методу в деревянных резервуарах, где она могла храниться гораздо дольше. Однако важнейшее наставление этого великолепного мастера навигации заключалось не в продвижении вдоль западного побережья Африки, что представлялось более коротким расстоянием, но где нужно было бы бороться с сильными встречными ветрами и течениями, а в использовании установленных им направлений превалирующих попутных ветров: северо-восточных от берегов Африки к югу от островов Зеленого Мыса, с тем чтобы совершить далекий обход по Атлантическому океану по резко юго-западному курсу до примерно 20 градусов южной широты, а оттуда поставить себе на службу юго-восточных помощников для поворота к юго-востоку и затем к востоку на мыс Доброй Надежды. Проверенный опытом да Гамы путь был значительно длиннее, но и гораздо более быстрым.
Вооруженный этими инструкциями, Кабраль миновал острова Зеленого Мыса примерно 22 марта, а 21 апреля его экипажи заметили появление птиц и обильных масс водорослей, что свидетельствовало о близости земли, а к концу следующего дня дозорный на мачте громким криком сообщил всему экипажу, что он видит землю. Справа по борту все теперь увидели высокий конусный контур горы — берег был теперь совсем рядом, и флотилия направилась в сторону возникшей на горизонте высоты и, проявляя осторожность перед появлением возможных рифов, до наступления темноты встала на якорь примерно в 20 милях от берега. Это произошло в среду на Страстной неделе перед пасхальным Воскресеньем, что и определило название конусообразной горы, данное ей Кабралем: Монтэ Паскуаль — Пасхальная Гора. На следующее утро каравеллы продолжили продвижение к берегу и снова бросили якоря на стоянку в полутора милях от песчаного пляжа прямо напротив устья небольшой реки с индейским именем Каи.
Кабраль и его спутники приняли открытую ими землю за остров, и, следуя тогдашней традиции, он назвал ее островом Вера Крус, то есть островом Истинного Креста в честь одноименного религиозного праздника, выпавшего на день его открытия. На берегу быстро собралась большая толпа заинтригованных появлением невиданных судов индейцев, и командующий флотилией посылает для переговоров с ними лодку с капитаном Николау Коэльу. Местные жители проявляли дружественное расположение, но Коэльу пришлось прервать начавшуюся встречу из-за поднявшихся сильных волн и быстро вернуться обратно на флагман. Начавшийся бурный ветер стал тащить парусники вместе с якорями. Дождавшись утра при ухудшении погоды. Кабраль со всей флотилией направился вдоль берега на север под юго-восточным ветром в поисках подходящей бухты, которая встретилась через примерно 40 миль от прежней стоянки. Бухта оказалась и большой и хорошо защищенной, что и определило данное ей Кабралем название — Порту Сегуру, или Надежная Гавань. Здесь экспедиция провела 8 дней, обследуя побережье и общаясь с дружественно настроенными индейцами племен тупи-гуарани. На прибрежном возвышении в устье реки Санта-Крус по приказу Кабраля был сооружен большой деревянный крест с вырезанным на нем гербом Португалии. Экипажам удалось сделать хорошую передышку перед длительным и, как оказалось, очень трудным плаванием в Индию. Понимая огромное значение сделанного им совершенно случайного, попутного открытия, Кабраль сразу же направил свое судно с припасами в Лиссабон для представления доклада королю, в котором содержались, среди прочего, довольно подробные сведения о новой земле, ее людях, природе, животных и растениях.