Madeira-szigetek az Atlanti-óceán északi részén található, a Makaronézia néven ismert régióban, alig 400 kilométerre északra a Kanári-szigetektől és 520 kilométerre nyugatra Marokkótól.

Plinius megemlít bizonyos Lila-szigeteket, amelyek helyzete a Szerencsés-szigetekre vagy a Kanári-szigetekre utalva Madeira-szigetekre utalhat. Plutarkhosz (Sertorius, i.sz. 75) Quintus Sertorius katonai parancsnokra utalva elmondja, hogy miután visszatért Cádizba, „találkozott tengerészekkel, akik nemrég érkeztek az atlanti-óceáni szigetekről, szám szerint kettőről, akiket csak egy keskeny csatorna választ el egymástól és Afrika partjaitól 2000 km távolságra található. Áldott szigeteknek nevezik őket.” Az Afrikától való becsült távolság és a két sziget közelsége Madeira-ra és Porto Santo-ra utal, amely sokkal kisebb, mint maga Madeira, és attól északkeletre található.

A Madeirán talált tizedik vagy tizenegyedik századi egércsont-töredékek, valamint madeirai egerek mitokondriális DNS-e arra utalhatnak, hogy a vikingek érkeztek Madeirára (egereket hoztak magukkal), még Portugália gyarmatosítása előtt. Ez a hipotézis azonban hamis, mert „a széles körben elterjedt kereskedelmi útvonalaknak köszönhetően egy Skandináviából származó egér könnyen felszállhatott volna egy hajóra a mai Portugália területén, és áthajózhatott volna Madeira, valamint az Azori-szigetekre”. Arra a következtetésre jutnak, hogy nincs bizonyíték skandináv településre és hogy a portugálok vitték ezeket az egereket Észak-Európából Madeirára.

Van egy romantikus mese két szerelmesről, Robert Machimról és Anna d’Arfetről III. Edward angol király idejében, akik 1346-ban Angliából Franciaországba menekültek, egy heves vihar eltérítette őket az útjukról és a tengerpartra vetették őket Madeira azon a részén, amelyet később egyikük emlékére Machico-nak neveztek el.

1419-ben Tengerész Henrik két kapitányát, João Gonçalves Zarco-t és Tristão Vaz Teixeira-t egy vihar az általuk egy szigetre terelte, amit ők hálából, hogy megmenekültek a hajótöréstől Porto Santo-nak, vagyis a Szent Kikötőnek neveztek el. A következő évben egy expedíciót küldtek a sziget benépesítésére, és Bartolomeu Perestrello kapitánnyal együtt birtokba vették a portugál korona nevében. Az új telepesek „egy nehéz fekete felhőt figyeltek meg délnyugatra”. Vizsgálatuk során kiderült, hogy ez a nagyobb sziget, amelyet Madeirának hívtak.

A szigeteket 1420-ban vagy 1425-ben kezdték betelepíteni. 1433. szeptember 23-án az Ilha da Madeira (Madeira-sziget vagy „az erdő szigete”) név először szerepel a térképen.

Az első telepesek a három kapitány és családjaik, a dzsentri tagjainak egy kis csoportja, szerény körülmények között élő emberek és a királyság néhány egykori rabja volt.

A településen a királyság minden tájáról érkeztek emberek. A korai telepesek egy része Algarve-ból indult útnak. Sokan érkeztek a földesúri rendszer foglalkoztatásának fontos feladatával. Szolgák, zsellérek, lovagok és nemesek azok, akik biztosították a települések megalakulását. Később Portugália északi részéből, nevezetesen Entre Douro és Minho régióból érkeztek telepesek.

A telepesek többsége halász és gazdálkodó volt, akik önként hagyták el Portugáliát, hogy új életet éljenek a szigeteken, reményeik szerint jobbat, mint lehetséges egy olyan Portugáliában, amelyet a fekete halál sújtott, és ahol a legjobb mezőgazdasági területeket szigorúan ellenőrizték a nemesek.

Ahhoz, hogy a szigeten minimális feltételeket teremtsenek a mezőgazdaság fejlődéséhez, a telepeseknek ki kellett vágniuk a sűrű erdő egy részét, és nagyszámú vízcsatornát kellett építeniük, hogy az északi part bőséges vizét délre szállítsák.

Kezdetben a telepesek búzát termeltek saját megélhetésükre, de később elkezdtek búzát exportálni Portugália szárazföldi részébe. Korábban a hal és a zöldség volt a telepesek fő megélhetési eszköze.

A gabonatermelés hanyatlásnak indult, és az ezt követő válság arra kényszerítette Tengerész Henriket, hogy más kereskedelmi növények ültetését rendelje el, hogy a szigetek nyereségesek legyenek. Az első vízhajtású cukorgyár bevezetését követően Madeirán a cukortermelés 1455-re több mint 6000 arroba-ra nőtt (egy arroba 11-12 kilogrammnak felelt meg), szicíliai tanácsadók segítségével és a genovai tőke finanszírozásával. (Genova a 17. századig a sziget gazdaságának szerves részeként működött.) Madeira megközelíthetősége vonzotta a genovai és flamand kereskedőket, akik szívesen megkerülték a velencei monopóliumokat.

„1480-ra Antwerpenben mintegy hetven hajó foglalkozott madeirai cukorkereskedelemmel, a finomítás és a forgalmazás Antwerpenben összpontosult. Az 1490-es évekre Madeira megelőzte Ciprust a cukortermelőként.”

A cukornádtermelés volt a sziget gazdaságának elsődleges motorja, amely gyorsan gazdasági jólétet biztosított Funchal városának. A cukornádtermelés Európa minden részéből vonzotta kalandorokat és kereskedőket, különösen az olaszokat, baszkokat, katalánokat és flamandokat. Ez azt jelentette, hogy a tizenötödik század második felében Funchal városa az európai kereskedelmi útvonalak kötelező kikötőjévé vált.