Но затем эти острова почти на тысячу лет были забыты, так как в средние века народы Европы, кроме норманнов и ирландцев, целыми столетиями не предпринимали дальних морских плаваний. Канарские острова были известны лишь по упоминанию о них в античной литературе. В XIV веке все Канарские острова вторично открыла португало-итальянская экспедиция. Неизвестные итальянские мореплаватели примерно в то же время посетили также необитаемые Азорские острова и Мадейру. Итальянские и каталонские моряки в те времена считались лучшими мореходами среди народов Средиземноморья, и португальские короли с начала XIV века охотно брали их к себе на службу. Португальские корабли с капитанами-итальянцами время от времени посещали Канарские острова и плавали вдоль северо-западного побережья Африки, на эти острова заглядывали и испанские мореплаватели – каталонцы и майоркцы, не обосновываясь, однако, здесь на жительство.
В 1344 году папа отдал Канарские острова графу де ла Серду, внуку кастильского короля, но тот не сумел получить ни малейшей выгоды из ленной области. Португалия яростно протестовала против этого дара, считая, что затрагиваются ее интересы. Однако острова не были колонизованы. Лишь в начале следующего – XV века нормандский граф Жан де Бетанкур, которого Кастилия поддержала людьми и оружием, прибыл на один из островов архипелага – Лансароти, построил форт и основал колонию на этом и еще одном из Канарских островов – Фуэртевентуре. Колонии просуществовали только пятнадцать лет. Бетанкур, осыпанный почестями при кастильском дворе, вернулся во Францию с титулом короля Канарских островов. Один из испанских магнатов откупил у Бетанкура право на владение ими, и так Кастилия, давняя соперница Португалии, приобрела удобную базу для океанских плаваний. Принц Энрики попытался захватить Канарские острова, ставшие яблоком нового раздора между обоими государствами.
Папа разрешил Португалии завоевать острова, и принц Энрики с переменным успехом неоднократно пытал здесь счастья.
В 1425 году он направил две с половиной тысячи воинов и сто двадцать коней на остров Гран-Канари, но попытка захвата не удалась, как в результате яростного сопротивления туземцев-гванчей, так и из-за недостатка в провианте. Несмотря на крупные расходы – только на транспорт было потрачено тридцать девять тысяч золотых крузаду, – принц два года спустя снарядил новую экспедицию, которая также не привела к успеху. Кастилия резко запротестовала против португальских помыслов, утверждая, что ей еще с самого начала века принадлежат два острова, Лансароти и Фуэртевентура, и что кастильский король много сделал для обращения островитян в христианскую веру. На самом же деле кастильцы безжалостно истребляли островитян-гванчей. Португалия, в свою очередь, подчеркивала, что острова бесхозны, что они никогда не принадлежали христианам, и поэтому их может захватить первый, кто там появится. Права же язычников-островитян ни той, ни другой стороной не принимались во внимание.
Нельзя установить точно, когда именно были открыты Мадейра и остров Порту-Санту к северо-востоку от нее и кто первым сделал это. Существовала легенда, будто штормом прибило к Мадейре корабль, на котором бежала из английского порта Бристоля одна влюбленная пара. Любовники умерли на острове, а их спутникам удалось достичь берегов Африки. Весть о Мадейре достигла слуха принца Энрики. Согласно другой легенде, любовники после Мадейры попали в Испанию и там рассказали о своем открытии. Есть смутные сведения о том, что острова Мадейры открыли арабские мореходы или, что более вероятно, итальянцы. На картах эти острова появились уже около 1350 года.
Хронист Азурара пишет, что в 1419 году Энрики послал на мыс Бохадор Жуана Зарку и Триштана Тейшейру, еще малоопытных моряков. Буря отогнала их корабль далеко на запад. Волей господа они, вопреки сильному ветру, достигли Порту-Санту и открыли, что он пригоден для колонизации. Они радовались тому, что здесь не было дикарей, как на Канарских островах, а птицы были непуганые, и их можно было ловить руками. О своем открытии они сообщили принцу. По приказу Энрики парусники вновь направились к Порту-Санту с различными семенами и домашними животными, в том числе кроликами, на борту. Эти грызуны позже так расплодились на острове, что от них не стало никакого спасения. Однажды Тейшейра с Порту-Санту заметил в океане у горизонта темную, тень и подумал – это либо туча, либо далекая земля. Колонисты построили лодки и поплыли искать новую землю. Они нашли остров и назвали его Мадейрой (по-португальски «лес»), так как там было много лесов с прекрасными деревьями, среди них было и легендарное драконово дерево с красной целебной смолой. Плодородная, щедро орошаемая водами земля обещала богатые урожаи.