Ensimmäinen historiallisesti luotettava lähde eurooppalaisten vierailusta Madeiralla on portugalilaisten saapuminen 1400-luvun alkupuolella. Madeirasta on kuitenkin myös huomattavasti vanhempia mutta epävarmoja viittauksia heti ajanlaskun alusta lähtien. Roomalainen kirjailija Plinius mainitsi teksteissään Purppurasaaret, jolla on hyvinkin voitu sijaintinsa puolesta viitata Madeiraan. Arabien on väitetty löytäneen saaren jo 1000-luvulla ja nimenneen sen El Ghanemiksi ja myös viikinkien vierailun mahdollisuutta on pohdittu. Rikkaan englantilaisen aatelisneidon Anne d'Arfetin kerrotaan rakastuneen köyhään Robert Machimiin 1300-luvulla Englannissa ja paenneen tämän kanssa pakkoavioliittoaan Ranskaan. Heitä kuljettaneen laivan kerrotaan kuitenkin joutuneen ankaraan myrskyyn, jonka seurauksena se ajautui pois kurssilta ja haaksirikkoutui nykyisen Machicon kaupungin edustalle. Kaupungin onkin arveltu saaneen nimensä Robert Machimin mukaan. 1300-luvulla Madeira kuitenkin todennäköisesti jo tunnettiin, sillä se esiintyy jo vuodelta 1351 peräisin olevassa italialaisessa kartassa. Kartassa Madeira esiintyy nimellä Isola di Lolegname (puusaari), jonka lisäksi siinä näkyvät myös Porto Santo sekä Desertassaaret nykyisillä nimillään.[1]

 

João Gonçalves Zarcoa esittävä patsas Funchalissa. Zarco johti Porto Santon ja Madeiran löytäneitä portugalilaisaluksia.

Madeiran saariryhmän virallinen kirjoitettu historia alkoi vuonna 1418, kun portugalilaisen prinssin Henrik Purjehtijan palveluksessa purjehtineet João Gonçalves Zarco ja Tristão Vaz Teixeira ajautuivat myrskyssä Porto Santon saarelle, joka sai nimekseen Porto Santo eli Pyhä satama. Seuraavana vuonna saarille järjestettiin tutkimusmatka. Italialainen aatelismies Bartolomeu Perestrello sai tehtäväkseen asuttaa Porto Santon ja Zarco ja Teixeira lähetettiin tutkimaan Madeiraa.[2]

Saaret olivat löydettäessä täysin asumattomia, ja portugalilaiset aloittivat niiden asuttaminen 1420-luvulla.[3] Uudisasukkaat toivat saarelle Italiasta sokeriruo'on ja Kreetalta viiniköynnöksen. Madeiralla oli pian suuria sokeriruokoviljelmiä, joissa käytettiin työvoimana Afrikasta 1450-luvulta lähtien[3] tuotuja orjia.[1] Madeiran taloudellinen merkitys kasvoi arvokkaan sokerikaupan myötä ja portugalilaiset saivat pian haltuunsa Euroopan sokerimonopolin.[1] Vuosina 1450-1470 Madeira oli huomattava viljantuotannon keskus ja viljaa vietiin muun muassa Manner-Portugaliin sekä Portugalin Afrikassa sijaitseviin kauppakeskuksiin.[1] Sokerinviljely oli kuitenkin huomattavasti kannattavampaa ja vuonna 1485 saaria vaivasi viljan puutteen vuoksi nälänhätä. Azoreista tulikin alueen vilja-aitta ja Madeira pystyi keskittymään arvokkaaseen sokerintuotantoon.[2] Funchalista ja Machicosta kehittyi vaurauden seurauksena kukoistavia kaupunkeja.[2]

1400-luvun lopulla Euroopasta virtasi Madeiralle lisää asukkaita. Monet heistä olivat kauppiaita, jotka toivat mukanaan lisää investointeja ja vaurastuttivat saarta.[3] Maine Madeiran hyvinvoinnista levisi ja houkutteli saaristoon merirosvoja.[1] Madeira kärsi pahimman merirosvohyökkäyksensä vuonna 1566, kun yli tuhannen hengen merirosvojoukko hyökkäsi Funchaliin ranskalaisen merirosvon Bertrand de Montluchin johdolla ja ryösti saarta yli kahden viikon ajan.[4]

Sokerintuotanto kukoisti 1450-luvulta lähtien, kunnes se 1500-luvun alkupuolella kääntyi laskuun.[2] Madeira menetti 1500-luvun aikana valta-asemansa sokeriruo’on tuottajana Brasilialle, jossa sitä voitiin tuottaa halvemmalla. Myös huono lannoitus ja ilmastolliset syyt vaikuttivat sokerituotannon romahtamiseen. Sokeriruoko oli kuluttanut Madeiran maaperää, jonka seurauksena useilla viljelmillä alettiin viljellä vähemmän vaativaa viiniköynnöstä. Madeira sai kuitenkin vielä 1500-luvun lopulla sokerista lähes seitsemän kertaa enemmän tuloja kuin viinistä. Madeira oli vuodesta 1580 vuoteen 1640 muun Portugalin tavoin Espanjan hallinnassa.[1]

Madeiran talous oli 1600-luvulla riippuvainen viinin viennistä sekä merenkulun tuomista tuloista.[1] 1660-luvulla Madeira oli joutua myötäjäislahjaksi Englannille, kun Englannin kuningas Kaarle II meni vuonna 1662 naimisiin Portugalin Katariina de Bragançan kanssa. Morsiamen myötäjäisiin kerrotaan liittyneen salainen sopimus, jonka mukaan Portugali olisi antanut Englannille lisäksi vielä Madeiran, mikäli Kaarle ei olisi ollut tyytyväinen myötäjäisiinsä.[1] Englantilaisen kauppiaiden vaikutus Madeiralla kasvoi 1600-luvun lopulta lähtien.[5] Madeira oli jo 1700-luvulla siirtolaisuus Brasiliaan kasvoi, sillä Madeira alkoi olla liikakansoitettu ajan olosuhteisiin nähden. Tästä huolimatta Madeiran väkiluku jatkoi kasvuaan. 1700-luvun puolivälissä asukkaita oli jo 75 000.[1]

Vuonna 1803 Madeiralla nousi ennennäkemättömän suuri tulva, joka aiheutti suurta hävitystä varsinkin Funchalissa. Ainakin 600 ihmistä sai surmansa. Britit miehittivät Madeiran kahdesti 1800-luvun alussa Napoleonin sotien aikana. Monia englantilaisia oli muuttanut Madeiralle jo 1700-luvulla lähinnä viininviljelijöiksi, ja Napoleonin sotien aikana ja niiden jälkeen heitä saapui lisää, kun monet brittisotilaista jäivät saarelle pysyvästi.[1] Jotkut sotien jälkeen Madeiralle saapuneista brittikauppiaista perustivat merkittäviä kauppiassukuja, kuten alkujaan liikekumppaneita olleet Charles Blandy ja Thomas Slap Leacock.[6]

1800-luvun kuluessa Madeirasta kehittyi suosittu matkailu- ja lomakohde, mutta lomailijat edustivat kuitenkin vielä pitkälle 1900-luvulle asti ylempää keskiluokkaa.[6] Madeiran kuvernöörinä toimineen José Silvestre Ribeiron aikana (1846-1852) rakennettiin teitä, pantiin alulle Funchalin sähkövalaistus sekä toteutettiin yhteiskunnallisia uudistuksia.[1] Vuonna 1852 riehunut kolera tappoi arviolta 7 000 ihmistä ja samana vuonna home tuhosi saaren viiniköynnökset, minkä seurauksena arviolta 90 prosenttia sadosta menetettiin. Yhdysvalloista vahingossa tuotu viinikirva saastutti ja tuhosi loput viiniköynnökset 1870-luvun alussa. Vaikka niiden tilalle istutettiin pian uusia lajikkeita, viljelmiä ei pystytty vielä palauttamaan täysin ennalleen ja 1800-luvun lopulla monien täytyi lähteä saarelta.[3] Vuonna 1900 saatiin kuitenkin jo ennätyssatoja ja saaren maataloustuotantoa monipuolistettiin istuttamalla lisäksi banaaneja, joilla on vielä nykyäänkin suuri merkitys viennin kannalta.[7]

Saksalainen yhtiö tarjoutui vuonna 1905 rakentamaan Madeiralle sairaaloita, parantolan sekä kehittää saaresta uudenaikaisen lomakohteen, mikäli se saisi vastaavasti ottaa haltuunsa kaikki saaren liiketoimet. Portugalin hallitus suostui aluksi ehdotelmaan, mutta ei ottanut huomioon Iso-Britannian mielipidettä.[7] Saksan kolonialististen tavoitteiden tultua lisäksi ilmi ehdotuksesta lopulta kieltäydyttiin.[5] Ensimmäisen maailmansodan alussa saksalainen omaisuus saarella takavarikoitiin. Saksa julisti Portugalille sodan vuonna 1916 ja samana vuonna saksalainen sukellusvene teki yllätyshyökkäyksen Funchaliin ja upotti satamassa kolme ranskalaisalusta sekä pommitti kaupunkia.[7][1] Vuonna 1917 saksalaiset sukellusalukset pommittivat Funchalia uudestaan tuhoten kaupungissa rakennuksia. Ensimmäisen maailmansodan jälkeen taloudellinen tilanne Madeiralla oli huono.[1]

Madeiralla puhkesi vuoden 1931 alussa yleislakko leivänhinnan nousun sekä kahden suuren madeiralaispankin konkurssin vuoksi.[8] Konkurssit olivat vieneet tuhansien madeiralaisten säästöt. Portugalista lähetettiin saarelle sotajoukkoja, mutta osa joukoista liittyi kapinallisiin, joita johti Portugalista karkotettu kenraali Sousa Dias. Portugalista lähetettiin lisää joukkoja ja kapina lopulta kukistettiin. Toisille myönnettiin turvapaikka Iso-Britanniasta, mutta useimmat Dias mukaan lukien joutuivat antautumaan portugalilaisille.[5] Portugali jäi toisessa maailmansodassa puolueettomaksi ja Madeira säästyi sotatoimilta. Madeiralle tuli poliittisia pakolaisia ja Iso-Britannia evakuoi sodan aikana Gibraltarin siirtokunnastaan noin 2 000 siviilihenkilöä Madeiralle.[1]

 

1970-luvun puolivälissä Madeiralla toiminut FLAMA-järjestö ajoi Madeiran itsenäisyyttä Portugalista suorittamalla saarella terrori-iskuja. Järjestön lippu muistuttaa Madeiran nykyistä lippua.

Portugalissa 25. huhtikuuta 1974 tapahtunut neilikkavallankumous kaatoi maata hallinneen sotilasjuntan. Oikeistolainen puolisotilaallinen FLAMA-järjestö suoritti Madeiralla terrori-iskuja tavoitteenaan saavuttaa itsenäisyys ja täydellinen riippumattomuus Portugalista. Kun Portugali sai vuonna 1976 uuden perustuslain ja Madeiralle määriteltiin autonominen asema, järjestön toiminta lakkasi.[8] Vuonna 1986 Madeira liittyi Portugalin mukana Euroopan unioniin.[1] Tämän jälkeen Madeira alkoi saada taloudellista tukea paremman infrastruktuurin ja uusien teiden rakentamiseen sekä sähkönjakelun, sairaanhoidon ja koulutuksen parantamiseen.[3] Madeiran elintaso onkin noussut autonomian ja EU-jäsenyyden aikana.[9]

Madeiraa koettelivat 20. helmikuuta 2010 voimakkaat rankkasateet, jotka synnyttivät pahoja tulvia ja mutavyöryjä etenkin saaren eteläosassa. Pahimmat tuhot keskittyivät pääkaupunki Funchaliin. 42 ihmistä sai surmansa, noin 120 ihmistä loukkaantui ja yli 200 ihmistä menetti kotinsa myrskyn vuoksi. Kyseessä oli pahin myrsky vuoden 1993 jälkeen, jolloin kahdeksan ihmistä sai surmansa.[10][11] Kesällä 2012 Madeiraa koettelivat poikkeuksellisen kuivan vuoden vuoksi Manner-Portugalin tavoin laajat maastopalot, joita sammuttamaan lähetettiin palomiehiä myös mantereelta.[12][13][14]