La muralla árabe fue construida por el emir Mohamed I entre los años 852 y 886. La muralla constituye el resto arquitectónico más antiguo de la ciudad de Madrid. Actualmente existen algunos vestigios que pueden ser visitados. Otros se encuentran enterrados por construcciones nuevas, formando parte de sus cimientos o de algunos de los paramentos localizados en los sótanos del edificio. La piedra de esta muralla ha sido también utilizada para los cimientos de muchos edificios de la zona.

Una de las zonas con mejores accesos para la visita se encuentra en la Cuesta de la Vega, enfrente de la Cripta de la Catedral de la Almudena. Los restos que han llegado hasta nuestros días se corresponden con un lienzo de unos 120 m de largo por 8 m de alto. Este lienzo ha sido restaurado en varias ocasiones, con criterios diferentes, sustituyendo los elementos dañados con ladrillo, con distintas variedades de calizas o rellenando las lagunas de la mampostería con morteros de colores variados.

Cuando se construyó el aparcamiento de la Plaza de Oriente (1994-1997), se desenterraron algunos restos de esta muralla, que han sido conservados y pueden ser visitados entrando por el paso de peatones existente delante del Teatro Real.

La muralla está levantada fundamentalmente con mampuestos de sílex y de caliza cretácica. En los zócalos de los torreones se aprecia una mayor elaboración de los paramentos, con construcción de sillarejos e incluso de sillares. En la denominada Cuesta de los Ramones, en el nº12 de la calle de Bailén, cerca del viaducto, puede apreciarse un zócalo de sillería de sílex. Estos sillares llegan a medir cerca de un metro y presentan un corte bien realizado, a pesar de la complejidad que debía suponer trabajar esta piedra de tan elevada dureza en aquella época.

En el muro existente en los Jardines de Mohamed I, se puede apreciar que la base está realizada con sillarejos de sílex. En las zonas superiores, estos sillarejos son sustituidos por una caliza de tonos blancos, correspondiente con la Piedra de Redueña, caliza cretácica que se encuentra asociada a los niveles de sílex en las explotaciones.

La muralla ha sufrido importantes expolios y daños generados principalmente por el crecimiento de la ciudad. Después de la actuación realizada en 1988 en los paramentos de la Cuesta de la Vega, el deterioro de sus materiales ha continuado. Actualmente, puede apreciarse cómo los sillarejos de calizas blancas de los niveles superiores sufren importantes pérdidas de volúmenes y pulverización de su superficie.

Existen pintadas en el zócalo de sillería de sílex en la zona de la calle de Bailén nº12, donde también los ladrillos y mampuestos existentes presentan un estado de conservación deficiente.