A 9. század második felében, I. Mohamed cordobai emír uralkodása (852-886) idején épült egy katonai erőd, arab nevén Mayrit vagy Magerit — feladata az volt, hogy védje a mór birodalom akkori regionális fővárosát, Toledót az északi keresztény királyságok támadásaitól.
A keresztény VI. Alfonz kasztíliai király 1083 körül szerezte meg a várost — nem egy nagy csata, hanem elsősorban tárgyalások és politikai alkuk eredményeként, ami rácáfol a Reconquista epikus, kizárólag fegyverrel vívott históriájára.
Madrid ezután évszázadokon át kasztíliai mezőváros maradt, saját városi kiváltságlevéllel (1202) és néhány alkalommal a vándorló királyi gyűlés, a Cortes helyszínéül szolgálva, de politikai súly nélkül.
A valódi hatalmi központok másutt voltak: Burgos, Toledo — amely 1085-től egészen 1561-ig, Kasztília, majd az egyesített Spanyolország tényleges fővárosaként és egyben az ország egyházi központjaként funkcionált —, illetve időszakosan Valladolid és a kereskedelmi nagyhatalom Sevilla. Madridnak a középkorban jelentős zsidó és mudéjar (muszlim) közössége is volt, előbbieket az 1391-es országos pogromhullám, majd az 1492-es kiűzető rendelet, utóbbiakat az 1502-es kényszertérítési rendelet számolta fel — Madridban a zsidó lakosság nagy része inkább a katolikus hitre térést választotta a távozás helyett.
Egy király egyszerűen odaköltözött
1561-ben II. Fülöp spanyol király Madridba, a régi mór erőd helyén álló alcázarba helyezte át az udvarát — és ezzel, szigorúan véve, semmi hivatalosat nem tett. Nem adott ki dekrétumot, nem nyilvánította fővárossá a várost: egyszerűen odaköltözött, és Madrid ettől kezdve de facto, a gyakorlatban vált Spanyolország kormányzati központjává. A döntést minden bizonnyal a földrajzilag központi fekvés indokolta leginkább, de szerepet játszott benne az is, hogy Madrid — szemben Toledóval, ahol az érsekség hatalma korlátozta a királyi akaratot — nem kötődött már kialakult egyházi vagy nemesi érdekcsoporthoz, így "tiszta lapként" lehetett rá építeni egy uralkodó-központú államot. A várost bőséges, mór eredetű vízhálózata és a közeli vadászerdők is vonzóvá tették. A fővárosi rang átmenetileg meg is szakadt: III. Fülöp és kegyence, Lerma hercege 1601 és 1606 között Valladolidba helyezte át az udvart — a történetírás szerint jó eséllyel azért, mert Lerma előre felvásárolt ingatlanokkal jelentős haszonra tett szert mindkét költözésen.
Az udvar beköltözése után Madrid gyors növekedésnek indult: lakossága az 1561-es 18-20 ezerről 1598-ra, II. Fülöp haláláig már 80 ezer fölé emelkedett. A valladolidi kitérő idején a népesség átmenetileg a felére esett vissza, majd a végleges visszatérés (1606) után a növekedés folytatódott, és 1630-ra meghaladta a 130 ezret. Ekkor épült a ma is álló Plaza Mayor (1617-1619), és itt élt, dolgozott a spanyol aranykor (Siglo de Oro) szinte teljes írógárdája — Cervantes, Lope de Vega, Calderón de la Barca —, akiknek emlékét ma is őrzi a főváros "Irodalmi negyede" (Barrio de las Letras).
IV. Fülöp minisztere, Olivares grófherceg emeltette a Buen Retiro-palotát és kertjeit (1630-tól) — deklaráltan azzal a szándékkal, hogy a lakosság szélesebb köre is élvezhesse, szemben II. Fülöp zárt, magányos Escorialjával. A 17. század második felében azonban Spanyolország és Madrid is súlyos hanyatlásnak indult: az ország népessége 8,5 millióról 6,6 millió alá csökkent, és 1700-ban, örökös nélkül elhunyt II. Károlyval kihalt a Spanyol Habsburg-ház — halála a Spanyol Örökösödési Háborút indította el, ami alatt Madrid kétszer is átmenetileg ellenséges (Habsburg-párti szövetséges) csapatok kezére került, mindkétszer csak rövid időre.
