Henrik Purjehtijan ensimäinen onnistunut yritys oli Porto Santon ja Madeiran löytö. Hänellä lienee ollut salainen tieto saarien olemassa olosta. Tapaturman kautta oli sinne ajautunut Machin niminen englantilainen, jonka surullisesta kohtalosta on säilynyt seuraava tieto:
Kuningas Edward III:nnen aikana pakeni Bristolista Robert Machin niminen mies, mukanaan erinomaisen kaunis, Anna d’Arfet niminen nainen. Mutta alus, jolla he yrittivät päästä Ranskaan, joutuikin myrskyn valtoihin ja ajautui kauas etelään, aina Madeira saarelle saakka, jossa nainen uupumuksesta kuoli ja rakastaja muutaman päivän perästä surusta heitti henkensä. Eloon jääneet laivamiehet purjehtivat pois, mutta kärsivät haaksirikon Afrikan rannalla ja joutuivat maurien vangiksi. Siellä heidän seikkailunsa kuuli eräs espanjalainen purjehdusluotsi, joka niinikään oli maurien orjana, mutta pääsi vapaaksi ja prinssi Henrikin laivureille kertoi jutun. Machin, jonka nimen saarella on perinyt Machicon kaupunki, ei kuitenkaan ollut ensimäinen, joka Keskiajallakaan kävi Madeirassa. Italialaisille kartoille oli saari jo neljännentoista vuosisadan keskivaiheilla piirretty ja »Puusaareksi» nimitetty. Mutta löytö oli joutunut unhotuksiin.
V. 1418 purjehti kaksi prinssi Henrikin hoviin kuuluvaa ylimystä, Zarco ja Vaz, etsimään Guinean rantaa, mutta jo lähellä Lagosta he joutuivat myrskyyn, joka ajoi laivan Madeiran koillispuolella olevaan pieneen Porto Santo saareen. Zarco ja Vaz ilomielin palasivat Sagresiin ja vakuuttivat, että heidän löytämänsä saari hyvin sopi asuttavaksi. Heidät lähetettiin sen vuoksi takaisin, mukanaan siirtolaisia, viljaa, mehiläisiä, Sisilian sokeriruokoa ja Kreetan viiniköynnöstä, vieläpä Portugalin kaniinejakin. Tällä matkalla oli mukana purjehdusluotsi Morales, jonka Zarco paluumatkallaan oli pelastanut vankeudesta.
Kun oli palattu Porto Santoon ja ryhdytty saarta asuttamaan, niin kiintyi huomio tummaan juovaan, joka näkyi lounaassa taivaanrannalla. Edellisellä matkalla saarelle jätetyt siirtolaiset olivat sitä katselleet joka päivä, kunnes päättivät varmaksi, ettei se saattanut olla pilven lonka. Morales paikalla arveli, että se mahtoi olla Machinin saari. Levättyään Porto Santossa kahdeksan päivää Zarco sen vuoksi päätti lähteä toisella laivallaan tiedustusmatkalle. Kauaa ei tarvinnutkaan purjehtia, ennenkuin auer selvisi saareksi ja saavuttiin Madeiran itäpäähän. Kun oli jonkun matkaa edelleen purjehdittu, niin löydettiin se ristikin, joka oli Machinin ja hänen lemmittynsä haudalle pystytetty. Zarco juhlallisesti julisti saaren Portugalin kruunun omaisuudeksi.
Lähdettiin sitten tutkimaan saaren rantoja ja tultiin muun muassa paikkaan, jossa kasvoi runsaasti saksan kuminaa; paikka siitä nimitettiin Funchaliksi — se on Madeiran nykyisen pääkaupungin nimi. Madeira on uljasta vuorimaata, jonka vanhat tulivuorikeilat kohoavat lähes 2000 metriä korkealle; rinteet ovat enimmäkseen jyrkät, rotkoiset, mutta siellä täällä on erinomaisen hedelmällistäkin maata, ja Portugalilaisten tullessa saarelle siellä kasvoi koskemattomat valtavat metsät. Lähetettiin retkikunta saaren sisäosiin tiedustelulle ja se palasi sillä tiedolla, että vuorille näkyi joka puolelta merta. Madeira ei olekaan kuuttakaan penikulmaa pitkä, paria leveä. Zarco otti muutamia näytteitä saaren kasveista ja palasi Portugaliin kertomaan prinssille uudesta löydöstään. Prinssi Henrik otti hänet suurella ilolla vastaan ja nimitti hänet Madeiran maaherraksi koko elinajakseen. Hänen toverinsakin saivat auliita palkinnoita. Zarco v. 1421 palasi takaisin saarelle ja alkoi rakentaa linnaa, ja neljän vuoden päästä prinssi Henrik lähetti siirtolaisia, sillä Madeira oli silloin aivan asumaton. Ensimäiset lapset, jotka saarella syntyivät, saivat kasteessa nimekseen Aadam ja Eeva. Tuskin oli saarella kauaakaan oltu, niin pääsi kulovalkea sen suuriin metsiin, ja ne paloivat kertomuksien mukaan seitsemän vuotta, valaisten kuin tulivuori tietä prinssi Henrikin laivoille, niiden purjehtiessa uusille löytöretkille. Metsien menetys oli suuri tappio, sillä kaikilla ympärillä olevilla mannerrannoilla oli puutavara kalliissa hinnassa. Mutta niitä ennätettiin kuitenkin sen verran hakatakin, että puutavaran hinta Portugalissa melkoisesti aleni ja maan koko rakennusmallikin muuttui puutavaran runsauden vuoksi. Palojen jälkeen oli maata helpompi raivata ja saarelle tuotiin sokeriruokoa, viiniköynnöstä, viljaa, hedelmiä. Kaikki siellä menestyi oivallisesti, sillä Madeiran ilmanala on lauhimpia, mitä on olemassa. Mutta kaniinit lisääntyivät niin tuhottomasti, että niistä pian tuli oikea maanvaiva. Ne tuhosivat kaikki viljelykset, kunnes siirtokunnat sen verran vaurastuivat, että saattoivat ruveta niitä hävittämään.
Henrik Purjehtijan myöhemmille yrityksille oli Madeiran löytö ja asutus erinomainen virike, sillä se oli omiaan hänen maanmiehilleen osottamaan, etteivät nuo puuhat suinkaan olleet hyödyttömiä.
Kap Bojador.
V. 1428 Prinssi Henrikin veli palasi eräältä ulkomaan matkalta ja toi mukanaan paljon kirjoja ja karttoja, joitten joukossa lienee ollut eräs Veneziassa laadittu aikaansa nähden etevä maailman kartta. Tämä kartta sisälsi seikkoja, jotka kehottivat prinssiä lähettämään laivojaan löytöretkille sekä länteen päin Atlantin merelle, jossa muka piti olla suuri saariryhmä, että etelään päin pitkin Afrikan rannikkoa.
Prinssi koetti ensinnäkin saada kapteenejaan purjehtimaan Bojadorin niemen ohi, jota kauemmaksi ei yksikään heistä ollut ennen yrittänyt, koska niemi oli kovin vaarallinen virtauksiensa ja salakariansa vuoksi. Sen ohi kulkee pohjoisesta tuleva merivirtaus, Golf-virran etelää kohti kääntyvä jatko. Mutta kauan sai prinssi suotta kehottaa ja käskeä laivureitaan, ei yksikään uskaltanut laskea pelätyn niemen ohi, sillä sen kiertäminen vaati ulkonemaan kauas valtamerelle, ja vielä suurempana syynä oli taikauskoinen pelko. Niemen toisella puolella pelättiin kuumuuden ja muitten esteitten vuoksi olevan mahdotonta purjehtia. Vaikka sitä ennen oli löydetty sekä Canarian saaret että Madeira ja sitä varten purjehdittu paljon ulommaksi merelle, niin ei vain ollut sitä miestä, joka olisi uskaltanut purjehtia tämän pelätyn kärjen ohi. Merimiesten kesken puhuttiin, että jokainen kristitty, joka Bojadorin nokan ohi purjehti, oli muuttuva mustaksi ja elämänsä loppuun kantava tätä Jumalan kirouksen leimaa. Arabialaisilla kartoilla, joita paljon käytettiin, oli niemen taa merkitty mereen kaikenlaisia hirviöitä, yks’sarvisia, käärmekallioita ja paholaisen käsi, joka uhkasi tuholla, haaksirikolla ja kadotuksella jokaista, joka uskalsi yrittää niemen ohi. Ja yhtä pelättävä kuin meri oli muka kuuma maakin, joka oli sen rannalla. Maantieteilijäin luulon mukaan oli ainoastaan pohjoisosa Afrikasta asuttua: Saharan reunasta alkoi asumaton maa, joka oli täynnä kaikenlaisia hirmuja, pahoja henkiä ja aaveita. Aurinko muka valoi maahan sulaa tulta, jonka vaikutuksesta joet ja meri kiehuivat yöt päivät kuin tulikuuma kattila. Jokainen merimies, joka uskalsi lähteä tuohon kuivaan vyöhykkeeseen, joka aina Kreikkalaisten ajoista saakka oli kartoilla pelotellut, oli varmaan menettävä yrityksessä henkensä.
Prinssi oli lähettänyt Gil Eannes nimisen kapteeninsa purjehtimaan Bojadorin nokan ohi, mutta näiden kuvittelujen vuoksi laiva ei uskaltanut yrittääkään, vaan palasi jotenkin huonoilla verukkeilla takaisin. Mutta silloin prinssi suuttui ja lähetti samat miehet oikopäätä uudelleen matkaan, ja tällä kertaa oli menestys parempi. Eannes teki meren kautta pitkän kierroksen, saapui onnellisesti niemen toiselle puolelle ja löysi sieltä rantavesiä, joilla hänen ihmeekseen oli aivan yhtä helppo purjehtia kuin kotovesillä. Ja maa oli kaunis ja vihanta. Asukkaita ei näkynyt, mutta maan kasveja otettiin laivoihin näytteiksi ja palattiin sitten takaisin. Näin oli vanha merimiespeljätys vihdoinkin voitettu. V. 1435 Eannes lähti uudelleen matkaan suuremmalla laivalla. Onnellisesti kuljettiin nytkin niemen ohi ja saavuttiin lahteen, jossa oli paljon kalaisia kareja, mutta palattiin sitten takaisin Lagokseen. Vielä samana vuonna lähetettiin Baldaya jatkamaan löytöjä ja hän saapui lahteen, joka nimitettiin Rio d’Ouroksi —samaa nimeä se vieläkin kartoilla kantaa. Siellä nähtiin ihmisiä, vaikka heitä ei saatukaan kiinni prinssille näytteeksi, kuten käsketty oli. Vaikka purjehdittiin vielä hyvä matka etelää kohti, niin ei kuitenkaan saatu kiinni maanasukkaita, vaan Baldayan täytyi sen puolesta palata takaisin tyhjin toimin. Tangerin vallottaminen ja muut valtiolliset huolet estivät prinssiä seuraavina vuosina jatkamasta näitä löytöretkiä.