El origen de la muralla se remonta a la época de 'Abd AllÄh', último cuarto del siglo IX. Aquella muralla se arruinó como consecuencia del terremoto de Constantinopla (1170) que afectó a todo el Magreb y la mayor parte de la península Ibérica, por lo que fue reconstruida por los almohades. El nuevo recinto amurallado, probablemente de mayor envergadura que el primigenio, nos es descrito por primera vez por Jimena Jurado en el siglo XVII: "tiene 1060 pasos de a cinco tercias de ancho en saliente oriental. 150 pasos. en el septentrional 290. en el occidental 290. en el Meridional 430. Esta junto al mismo rio en la ribera septentrional. Tiene en las cuatro esquinas 4 torreones achavados muy solidos".

La muralla, construida en dura argamasa tenía un perímetro de 1.740 metros, contaba con 48 torreones y, muy probablemente, de seis puertas: Sol, Santa Clara, Alcázar, Córdoba, Arco Grande y Peso la Harina.

De todo ese conjunto de murallas hoy solo se ha mantenido:

El Torreón Tavira y el Torreón de la Fuente Sorda.

Un lienzo de 5 metros que linda con la antigua carretera Madrid-Cádiz y con las calles Muralla y Ronda de Muralla (Muralla del Alcázar).

Dos torreones y 3 lienzos en el callejón Silera, detrás del Palacio de los Niños de Don Gome (el Torreón de Don Gome y el Torreón Silera).

Restos de un torreón en la calle del Hoyo (Torreón del Hoyo), sobre el que hay un gran mural de azulejos con un antiguo plano de la Muralla.

Lienzo de la Muralla Almohade - Altozano Marquesa
Sobre este lienzo vemos por donde originariamente transcurría la muralla, asi como las diferentes puertas de acceso a la ciudad, los torreones, e incluso la situación del Castillo.
Es el mayor tramo de muralla conservado y el que mejor presenta su imagen original, de tiempo de los almohades. Actualmente tiene 60 metros, los cuales engloban dos torres intermedias y tres tramos de muralla, con toda seguridad colindantes con la torre ochavada, cerca de la puerta del Sol Los muros sin almenar permiten ver la factura de tapial y argamasa, conservando su camino de ronda, aunque en mal estado, y las cámaras altas y terrazas de las torres, el paso de ronda se abre en la parte central del cubo para dar acceso a la cámara del torreón, con un arco de ladrillo como se adivina de los rastros dejados en el calicanto el vano, En el interior se deduce de las ruinas una cámara con cúpula y paredes de ladrillo desde la cual se accede a la terraza por dos escaleras laterales en forma de "L". La parte superior de los torreones esta coronada por almenas, reforzada por tres espigones de ladrillo en sus caras exteriores apoyados sobre un sillar bien tallado, todo ello empotrado en el calicanto del muro.