thumb|Alegoría de la villa de Madrid (1810), por Goya (Museo de Historia de Madrid).
Si bien el área ya había sido ocupada por asentamientos previos, la historia de Madrid como núcleo urbano habitado de forma continuada tiene su inicio en el , con la construcción de una fortaleza en la zona promovida por el emir Mohamed I, y está marcada por el establecimiento en ella de la corte real en 1561 y, con la consolidación del país, su transformación en la capital de la monarquía, capital a la que el antimadrileñismo habría tratado, en palabras de José Cepeda Adán, en clave de ciudad frívola y superficial, con «una historia sin historia, hecha de entradas solemnes, fiestas, carnavales y bullicio», si bien este autor destaca la importancia clave en la política estatal de numerosos episodios históricos acaecidos en la ciudad, al punto de considerar a Madrid epicentro de todas las revoluciones. En la actualidad es la ciudad más poblada de España.
Los orígenes de la ciudad son objeto de revisión tras los recientes hallazgos, en su perímetro más antiguo, de enterramientos visigodos así como de restos que se remontan a los carpetanos o periodo prerromano. Las excavaciones arqueológicas en el término municipal también arrojan restos romanos en diferentes distritos de la ciudad moderna, atribuyéndose al Madrid romano, y sobre la base de los restos encontrados durante las obras de soterramiento de la autopista M-30, una localización a orillas del río Manzanares en el área de influencia del puente de Segovia, en el entorno hoy ocupado por el parque de Atenas, la parte baja de la calle de Segovia y el paseo de la Virgen del Puerto. El Madrid romano no se situaría por tanto en el posterior enclave en altura del periodo visigodo para situarse en el valle del Manzanares, a escasos metros de donde se documentan los referidos restos visigodos, en la colina formada por los actuales Palacio Real y catedral de la Almudena. Estos recientes hallazgos de época visigoda han venido a confirmar las teorías de varios autores que sostuvieron que el posterior asentamiento fortificado musulmán de Maǧrīţ (del ) se había fundado sobre un vicus visigodo del llamado Matrice o matriz, arroyo. (AFI ).Escrito en árabe: مجريط; llamado también en castellano antiguo Magerit o Matrit, se había asentado sobre un anterior vicus visigodo del llamado Matrice o 'arroyo'.
No sería hasta el cuando Madrid es incorporado a la Corona de Castilla, tras su reconquista por los hispanos cristianos, procedentes de Segovia y comandados por Día Sanz y Fernán García, siendo rey Alfonso VI de León, en 1083. A partir de ese momento es cuando Madrid comienza un proceso lento pero constante de crecimiento en su territorio, población e influencia, que abarca todo el periodo medieval hasta situarse a fines del como una de las principales ciudades de Castilla. Resultado de este proceso de crecimiento, entre otras razones, sería su designación como sede de la Corte por Felipe II en 1561, convirtiéndose en la primera capital permanente de la monarquía española. Desde ese mismo año de 1561, Madrid experimentó un crecimiento exponencial en tamaño y población, que alcanzaría a finales del más de medio millón de habitantes sobre el suelo de la ciudad consolidada (ciudad antigua más ensanche). Madrid, por tanto, ha sido desde el Renacimiento () y hasta la actualidad, capital de España y sede del Gobierno y la administración del Estado, salvo un breve intervalo de tiempo entre los años de 1601 y 1606, en los que la capitalidad pasó a Valladolid así como durante la Guerra Civil, cuando el Gobierno de la República se trasladó primero a Valencia y después a Barcelona, y al finalizar la guerra es Burgos la ciudad que ostenta la capitalidad.
Orígenes legendarios
Como en otras ciudades europeas, sobre todo, para poder compararse con orígenes mitológicos de grandes capitales, durante el Renacimiento, se buscaron supuestos orígenes míticos de la villa. Se redoblaron esfuerzos, sobre todo, a partir de que, en 1561, Felipe II estableciera en Madrid la sede permanente de la Corte, en ese momento, la más poderosa del mundo.
La primera leyenda fue confeccionada por el archivero e historiador Francisco Tarafa en su obra De origine ac rebus gestis regum Hispaniae (Amberes, 1553), donde atribuye a un héroe y príncipe griego Ocno Bianor su fundación. Y será el clérigo e historiador Jerónimo de la Quintana, que en 1629 recoge la vieja leyenda fundacional de Ocno en su obra monumental A la muy antigua, noble y coronada villa de Madrid: historia de su antiguedad, nobleza y grandeza, considerada la primera enciclopedia sobre Madrid. Ocno, que aparece en el libro X de la Eneida de Virgilio,Virgilio, Eneida, Libro X: texto español en Wikisource; traducción de Eugenio Ochoa. era hijo de Tiberino, rey y dios del río Tíber y de la adivina Manto, hija a su vez del adivino tebano Tiresias. Su abuelo, según la literatura clásica, fue compañero de Eneas en Troya. Ocno, despojado de la corona de su padre, viajó con su madre, emprendieron viaje hasta que fundaron una ciudad, a la que denominaron Manto, la hoy denominada Mantua, a orillas del Mincio.
Ya maduro, en un sueño, Apolo le indicó que debía peregrinar hacia dónde muere el sol, para evitar una gran mortandad a su ciudad. De ese sueño viene el nombre de Ocno, "el que posee el don de ver el porvenir en los sueños". Para salvar a su pueblo, Ocno inició un largo peregrinaje en su búsqueda pope que Apolo se le apareció de nuevo en sueños indicándole que en ese preciso lugar fundara una ciudad, debía poblarla y ofrecerla a los dioses. Al despertar, contempló un lugar luminoso y bello, con agua abundante y rico en encinas y madroños. Vio pequeñas chozas habitadas por pastores y supo que eran carpetanos, “los sin ciudad”. Les avisó de los deseos de Apolo y se dispusieron a fundar la ciudad, la Mantua Carpetanorum, a la que dedicaron a la diosa Cibeles.
Según esta supuesta leyenda, Mantua primero y después Madrid, serían las ciudades europeas más antiguas, incluso antes de la fundación de la propia Roma. También caló en la intelectualidad, llevando el nombre de Mantua Carpetanorum en inscripciones y documentos como así lo atestigua el Plano de Madrid de Pedro Teixeira de 1656, que lleva la inscripción: Mantua Carpetanorum sive Matritum Urbs Regia.
Restos paleontológicos La ciudad de Madrid posee ricos yacimientos paleontológicos anteriores a la aparición del ser humano: en el Mioceno medio, hace unos 18 millones de años, donde se ubica el puente de Toledo habitaron faunas propias de un clima cálido y seco, destacando la abundancia de un tipo de rinoceronte sin cuernos que, al ser definidos aquí por primera vez, recibieron el nombre de Hispanotherium. Otros yacimientos importantes de las mismas fechas son los del cerro de San Isidro, La Hidroeléctrica, la calle Moratines, el apeadero de O'Donnell, la estación Imperial y el paseo de las Acacias (Arganzuela). En ellos hay presencia del mismo rinoceronte y otras faunas cálidas subtropicales, principalmente rumiantes, entre ellos los antílopes más antiguos conocidos en España y ciervos antiguos, pero también paleomerícidos y tragúlidos.
De hace unos 15 millones de años, datan los fósiles exhumados en el Puente de Vallecas, en los que dominan los équidos (Anchitherium ezquerrae) y los cérvidos (Heteroprox moralesi), indicando un cambio climático importante: frío y humedad.
De hace 13 millones de años, aparecen en la calle Alhambra una considerable cantidad de fósiles de tortugas gigantes terrestres (Geochelone bolivari), así como un peculiar rinoceronte sin cuernos pero de grandes incisivos (Aceratherium simorrense) y un antílope (Tethytragus langai) que parece haber desplazado a los ciervos.Embajadores hace 17 millones de años. Paleontólogos y Comunidad reconstruyen en un libro la vida prehistórica de Madrid
Prehistoria thumb|Bifaz achelense de del Cerro de San Isidro
Del Cuaternario existen hallazgos arqueológicos que prueban la existencia de población humana en las terrazas de los ríos Manzanares, Jarama y Henares desde el Paleolítico. Muchos de estos lugares son conocidos desde el y actualmente están bajo zonas urbanizadas, aunque, afortunadamente, el Museo Arqueológico Nacional conserva una buena provisión de fondos arqueológicos que están siendo revisados y que corresponden a una decena de yacimientos del Paleolítico Inferior y Medio. Además, el control de las obrasEl primer hogar de Madrid ELPAIS.com y de las explotaciones de áridos ha permitido descubrir lugares relativamente bien conservados.
Etapas romana y visigoda Ya en el periodo histórico,Madrid precristiano no existen evidencias de que existiera ningún poblamiento de entidad dentro del actual término municipal durante las épocas romana y visigoda. No obstante, sí que existen rastros de la existencia de poblamiento disperso. La vieja creencia de que el arroyo Meaques, en la Casa de Campo, pudo ser la venta romana (en latín, mansio) llamada Miaccum, situada sobre la vía que unía Titulcia con Segovia, no está desechada. El poblamiento romano identificado hasta ahora apunta a varias villae o casas de campo señoriales más o menos próximas al río Manzanares, en puntos como Ciudad Universitaria, puente de los Franceses y de Segovia, Puerta del Ángel y Camino del Robledal. Conocidas de antiguo son las villae de Villaverde Bajo y la llamada "Quinta de los Carabancheles", ambas con mosaicos (los de la segunda en el Museo Municipal de San Isidro).
En época visigoda se atribuyen los primeros restos de una basílica del periodo hispano-visigodo en el entorno de la actual catedral de la Almudena y que podría demostrar la evidencia de un asentamiento urbano en ese periodo. Otras muestras arqueológicas de la presencia de una población estable en Madrid son los restos de dos necrópolis visigodas, una en la antigua colonia del conde de Vallellano —paseo de Extremadura, junto a la Casa de Campo— y otra en Tetuán de las Victorias. También de época visigoda (fechada en el 697) es el primer documento escrito de Madrid: la lápida que se encontraba en el claustro de la iglesia de Santa María de la Almudena, probablemente hasta mediados del y que fue recogida por diversos autores durante el .Lápidas visigóticas de Guadix, Cabra, Vejer, Bailén y Madrid
Recientemente, se han comunicado a través de la prensa nuevos hallazgos prerromanos (cerámica de época carpetana) y visigodos (enterramiento) en las obras que se llevan a cabo en el entorno del Palacio Real. También se ha publicado en la prensa la aparición de una gran necrópolis visigoda en las inmediaciones del cerro Almodóvar, en Vicálvaro, al sureste de Madrid.
Época musulmana
thumb|Restos de la muralla musulmana de Madrid (siglo ), junto a la Cuesta de la Vega.|izquierda
La primera noticia histórica de lo que hoy es la ciudad de Madrid data de la época del Emirato omeya de al-Ándalus, concretamente de finales del siglo , cuando el emir cordobés Muhammad I (852-886) levanta una fortaleza o hisn en un promontorio junto al río Manzanares, en el lugar donde se alzan hoy la catedral de la Almudena y el arranque de la calle Mayor, cerca de los llamados altos de Rebeque.Testimonios del Madrid medieval miniaturadeimagen|Ilustración decimonónica idealizada de la toma de Madrid por Ramiro II en el año 932La función de esta fortaleza será la vigilancia de los pasos de la sierra de Guadarrama para proteger Toledo, la antigua capital visigoda. También la de Ribat, es decir, punto de reunión e inicio de las campañas contra los reinos cristianos del norte. Por ejemplo, en el año 977, Almanzor comienza su campaña en Madrid. Cuando el califato de Córdoba se desintegra, Madrid pasa a formar parte del reino taifa de Toledo. miniaturadeimagen|Ilustración decimonónica idealizada representando a Almanzor en Madrid