Don Juan de Guzmán y Torres, I señor de La Algaba, intercambia con el conde de Niebla el señorío de Medina Sidonia por otros varios señoríos, entre los que se encontraba el de La Algaba. Tal intercambio resulta sorprendente, ya que la importancia estratégica de Medina Sidonia le hubiera podido proporcionar a Don Juan una brillante carrera militar, por lo que este intercambio podría interpretarse como síntoma de un cambio de mentalidad en la nobleza castellana de querer alternar las actividades militares con otras mercantiles, obteniendo de estas últimas grandes beneficios económicos.

En 1565 el rey Felipe II otorga el marquesado de La Algaba a don Francisco de Guzmán y Manrique, que amplía el palacio y lo dota de jardines. Afortunadamente, entre 1998 y 2002 fue rehabilitado por la Gerencia de Urbanismo del Ayuntamiento de Sevilla, gracias al Plan Urban de fondos europeos, albergando desde entonces los Servicios Centrales de la Delegación de Participación Ciudadana del consistorio municipal.

La única parte que pudiéramos pensar que ha subsistido de aquel palacio medieval de la familia Guzmán podría ser la torre defensiva donde se abre la portada mudéjar, así como la caja de escaleras adosada a la misma, pero lo cierto es que hay distintas razones documentales para pensar que la citada torre y la caja de escaleras no formaran parte del palacio de los Guzmán, sino del palacio de sus vecinos Diego Mexía y Leonor Pineda, de quienes lo adquiriría posteriormente Doña Beatriz de Guzmán, hermana de Don Juan de Guzmán y Torres, para anexionarlo finalmente al nuevo palacio de estilo renacentista.

Respecto a la torre defensiva, pertenece a un tipo del que ya existían antecedentes en la ciudad andaluza desde el siglo XIII, como era la Torre de Don Fadrique, pero el uso de esta tipología de torres continuó debido al clima de rivalidad y continuas luchas que se mantuvo durante siglos entre las distintas familias nobles. No obstante, la torre del Palacio de los Marqueses de La Algaba, tal vez por ser más tardía, perdió su primitiva robustez en aras de un mayor refinamiento estético.

En cuanto a la portada mudéjar, hablamos de la más importante de la arquitectura mudéjar civil conservada en Sevilla después de la del Palacio del Rey Don Pedro en el Real Alcázar.

En el año 1989 se inician las gestiones de la venta del edificio por parte de su última propietaria, Doña María de los Ángeles Balbuena, al Ayuntamiento de Sevilla, operación que concluye en mayo del año siguiente. Desde entonces se inicia el proceso de rehabilitación integral del edificio con la financiación de fondos europeos del mencionado Plan Urban, terminándose la misma en el año 2003.

El Palacio de los Marqueses de La Algaba acoge en la actualidad los Servicios Centrales de la Delegación de Participación Ciudadana del consistorio hispalense. A este uso se ha añadido, desde el 11 de enero del pasado año 2013, el Museo del Arte Mudéjar, compuesto por un total de 111 piezas procedentes de distintos museos de la capital hispalense, como el Museo Arqueológico, el Museo de Bellas Artes y el Museo de Artes y Costumbres Populares, así como bastantes piezas rescatadas del Convento de Santa Clara tras su restauración.