S'ha dit, tot i que no n'hi ha proves concloents, que els fenicis van descobrir Madeira en una època ben primerenca. Plini esmenta unes illes Porpres o Mauritàniques, la posició de les quals amb referència a les illes Afortunades o Canàries sembla que vulgui indicar l'arxipèlag de Madeira. Hi ha una història romàntica, de veracitat més que dubtosa, que parla de dos amants, Robert Machim i Anna d'Arfet, que fugien d'Anglaterra cap a França el 1346 i es van desviar de la seva ruta a causa d'una violenta tempesta; van anar a parar a la costa de Madeira al lloc més tard Machico, en record d'un d'ells. Segons es pot comprovar en una carta portolana datada el 1351, que es conserva a Florència, sembla que Madeira havia estat descoberta força temps abans d'aquella data per vaixells portuguesos capitanejats per oficials genovesos. El 1419, dos dels capitans del príncep Enric el Navegant, João Gonçalves Zarco i Tristão Vaz Teixeira, es van veure desviats per una tempesta cap a l'illa que van anomenar Porto Santo, en senyal de gratitud per haver-se salvat del naufragi. L'any següent es va enviar una expedició per poblar l'illa i, com que des d'allà van albirar Madeira, també s'hi van dirigir i en van prendre possessió en nom de la Corona portuguesa. Hi fundaren la vila de Funchal (de funcho, fonoll),

La colonització de les illes va començar cap a 1432 o 1433. El 23 de setembre de 1433, el nom Ilha da Madeira (illa de Madeira, o "illa de la fusta") apareix en un mapa, per primera vegada, dins un document.

El 1425 s'inicià la colonització portuguesa, ja que, com les Açores, tenien força importància estratègica en el pas marítim cap a Guinea. El 1451 Funchal va rebre la carta de vila o concelho, fur que fou ampliat el 1472, i a l'illa s'hi introduïren ceps de vinya de Xipre, Creta, Borgonya i del Rin, així com la malvasia de Creta, els quals originarien el vi del país. El 1452, endemés, s'introduiria des de Sicília el conreu de sucre de canya a Machico.

El 1502 Bethencourt descobrí l'illa de Porto Santo per a Castella, però aquesta en renunciarà en favor de Portugal. El 1508 el rei portuguès Manuel I va concedir rang de ciutat a la vila de Funchal, mentre que el 1514 esdevenia seu episcopal. Quan Felip II de Castella fou proclamat rei de Portugal el 1580, els espanyols ocuparen l'illa, que fou atacada per l'anglès Preston, qui bombardejaria Porto Santo el 1592. Quan el 1640 els portuguesos es revoltaren contra els espanyols, Madeira tornaria a mans portugueses.

El 1801 foren ocupades temporalment per la Gran Bretanya per tal que no les ocupessin els francesos, fet que repetiria del 1807 al 1814, any en què foren tornades a Portugal pel Tractat de Versalles. Endemés, el 1803 un fort temporal va destruir temporalment Machico. El 1828 participarien activament en la guerra civil entre Pedro I i els miguelistes, i el 1852 patiria una plaga d'oïdium que malmetria la collita de raïm.

El 1873 també patiria una plaga de fil·loxera que provocaria una crisi econòmica tan forta que molts maderesos emigraren massivament cap a Amèrica del Nord i del Sud. El 1895-1898 es va suprimir temporalment el concelho de Porto Moniz i s'iniciaren els primers moviments autonomistes, de manera que la metròpoli els va concedir un petit autogovern.

El 1921, l'emperador austrohongarès Carles I fou deportat a Madeira, després d'un cop d'estat fracassat. Hi va morir un any després. El 1931 s'hi van sublevar els militars antisalazaristes, que es rendirien mercè la mediació del bisbe de Funchal. I durant el 1940-1945 foren emprades com a base aliada, encara que amb una importància relativa menor que les Açores.

Pel novembre del 1975, un cop triomfà la Revolució dels Clavells i va caure el govern salazarista, es fundaria el Frente de Libertação do Arquipélago de Madeira (FLAMA), com a reacció per l'arribada al poder a Portugal dels comunistes i esquerrans, amb suport no gaire dissimulat dels emigrats als EUA. Com a resultat, el 1976 va rebre del govern portuguès un fort estatut d'autonomia. Després del govern interí de Jaime de Ornelas Camacho (1911) de l'u d'octubre del 1976 al 3 de març del 1978, a les primeres eleccions venç el socialdemòcrata Alberto João Jardim (1943).

Pel febrer del 1978 el FLAMA edita el diari separatista Jornal Insular, que rep suport dels maderesos americans; alhora, el Movimento Independentista de Madeira (MIM) rep el suport dels radicals africanista i aconsegueix que Madeira sigui integrada amb el grup d'illes que s'havien d'independitzar seguint les pautes de l'OUA. Portugal, naturalment, rebutja el document.

Finalment, l'octubre del 1979, se celebra la Cimera de Funchal presidida per Alberto João Jardim, amb membres de l'OUA i del govern portuguès, i on es prenen els següents acords: definició de l'eix Açores-Madeira-Canàries i reforçar l'autonomisme per combatre l'independentisme.

Des d'aleshores, el moviment independentista s'apaivagà força, i a les eleccions autonòmiques del 1984 el PSD va obtenir 40 dels 50 escons maderesos, i A.J. Jardim fou reescollit president. El 9 d'octubre del 1996 Alberto João Jardim, president autonòmic des del 1978, sempre amb majoria absoluta, va tenir una forta oposició dels comunistes del CDU, presidit pels capellans Edgar Silva (33 anys) i Mário Tavares, a qui acusà de venut a l'església, cosa que provocà els ires del bisbe de Funchal, Teodoro de Faria; i de l'extrema esquerra UDP, dirigida pel també capellà Martins Júnior (58 anys).