Успех первого плавания Джона Кабота через Атлантику на службе английского короля вызвал немалое беспокойство Испании и Португалии, опасавшихся за утрату своей монополии на освоение путей в Индию и новых открытых земель. Согласно договору Тордесильяс, заключенному этими соперниками в 1493 году и освященному соответствующими папскими буллами, весь еще не открытый мир был поделен именно между ними. Поэтому попытки любой другой страны, в том числе Англии, претендовать на новые земли с точки зрения действовавшего тогда правового порядка являлось нарушением международного права и посягательством на законные интересы двух иберийских держав. Однако отстаивать эти интересы на огромных просторах Мирового океана и обширных открытых землях было далеко не простым делом, но и Испания и Португалия предпринимали посильные меры для защиты своих позиций. Появление третьего соперника подтолкнуло Испанию к скорейшей организации третьего плавания Колумба и активизации исследования и освоения новых территорий другими подданными ее короны. Португалия в свою очередь решила довести до успешного конца незавершенные многолетние усилия по прокладыванию пути в Индию вокруг мыса Доброй Надежды, заканчивая подготовку эпохальной экспедиции Васко да Гама. Одновременно с этим португальский король ждал возможности проверить открытие Джона Кабота, чтобы установить, предпочтительно за чужой счет, находилась ли открытая им новая земля в сфере пространств, закрепленных за его короной. Такая возможность ему вскоре представилась.
Жоау Фернандеш жил на Азорских островах, где владел землями, которые он сдавал в аренду местным крестьянам Его положение некрупного землевладельца, называвшегося по-португальски лаврадор, давало ему возможность заниматься торговлей товаров, которые он отправлял со своего острова Терсейра в Лиссабон, а также в английский порт Бристоль, откуда посылал местные товары в Португалию. После плавания Джона Кабота предприимчивый португалец обратился к своему монарху с просьбой предоставить ему жалованные грамоты «для поиска и открытия некоторых островов в нашей сфере влияния». Финансирование экспедиции, по всей вероятности, обеспечивал богатый аристократ и сосед Фернандеша по Терсейре Педру дэ Барселуш. В 1499 году эти грамоты были предоставлены, а в 1500 году оба партнера уже отправились в плавание со своего острова в северные широты Атлантики, к земле, открытой Джоном Каботом.
Сведений об этой экспедиции до нас дошло немного. Известно, что летом 1500 года она достигла юго-западной части забытой со времен Эрика Эриксона и теперь бывшей снова неведомой Гренландии. Поскольку эту землю первым увидел Жоау Фернандеш, путешественники решили назвать ее в честь морехода-землевладельца Лабрадором. Именно под этим именем Гренландия обозначалась на картах в течение нескольких последующих десятилетий. Лишь спустя более целого столетия географы, установив первоначальное скандинавское название этого острова, нанесли его на карты, а имя «Лабрадор» перенесли на соседний полуостров на континенте, который и сохраняет его по сегодняшний день. Отсюда экспедиция повернула на Ньюфаундленд, а затем направилась к континенту, надеясь отыскать пролив для выхода к Китаю и Индии. К этому времени плавание в тех широтах могло быть уже серьезно затруднено собиравшимися льдами, и партнеры, видимо, вынуждены были повернуть обратно в расчете вернуться в более благоприятный сезон и продолжить поиски.
При возвращении домой Фернандеш мог сообщить королю лишь о том, что была открыта покрытая льдами безлюдная «Земля Лабрадор» (Гренландия), что на открытом Каботом Ньюфаундленде английских поселений обнаружено не было, а сам остров не находился в португальской сфере раздела. Фернандеш планировал продолжить свои исследования, но ему стало очень скоро известно, что король Португалии уже предоставил подобные, но еще более широкие полномочия Гаспару Корте Реалу—придворному дальнему родственнику королевской семьи. Обиженный столь незаслуженным оскорбительным отношением к себе со стороны монарха, Фернандеш уезжает в Бристоль, где вместе с двумя соотечественниками с Азорских островов и тремя местными коммерсантами создает заинтересованную в продолжение исследований группу. В ответ на их обращение в марте 1501 года Генрих Седьмой предоставляет им соответствующие жалованные грамоты с очень широкими полномочиями и привилегиями. Согласно королевским бухгалтерским книгам, инициаторы этой идеи, которым делались определенные выплаты за их услуги на данном поприще, совершали экспедиции в течение последующих 3—4-х лет, но никаких других сведений об их плаваниях не осталось.