Este monumental caserón, de robusta estampa, perteneció a una rama menor de los Fernández de Córdoba, familia que arraigó de forma importante en la ciudad y poseyó un rico patrimonio en forma de bienes rústicos y urbanos. El edificio actual ocupó el solar de un antiguo palacio de época nazarí, propiedad de Hernán Valle de Palacios, morisco secretario del Zagal, que tras la primera rebelión mudéjar de 1490 fue desplazado a la morería de Santa Ana. Fue Juan Fernández de Córdoba el que levantó, al menos en parte, lo principal del palacio a mediados del siglo XVI. En el siglo XVIII lo habitó el Marqués de Villalegre, con lo que el edificio y la plaza pasaron a tomar ese nombre. Con el tiempo pasó a ser cuartel de la Guardia Civil y en los últimos años casa de vecindad, hasta que el Ayuntamiento lo adquirió para usos propios.
Su construcción fue lenta y se prolongó a lo largo del siglo XVI, sin que llegara a terminarse hasta época bastante reciente. Su apariencia externa es sobria, pero no carente de monumentalidad por la potencia de las dos torres de flanqueo, que de forma airosa presiden su fachada. Su planta define un amplio cuadrángulo presidido por un patio de moderadas dimensiones, en torno al cual se levantan las dependencias en dos plantas, más los torreones ya indicados. Sus muros laterales muestran la fábrica habitual de cajones de tapial encintados de ladrillo, mientras que en la principal se emplea el ladrillo en exclusividad para poder jugar con más elegancia con los vanos y portada. La disposición de las ventanas en el costado norte, sin respetar la distribución de cintas y rafas del ladrillo, indica que su apertura se realizó con posterioridad a la primera fábrica, la cual debió ser mucho más cerrada que en la actualidad.
El elemento más destacado del exterior es la potente fachada, toda labrada en ladrillo sobre un zócalo de sillería añadido recientemente. Se articula en aparente simetría, con una portada central y balcón encima, todo de cantería, como complemento de prestigio, y dos pisos que se alargan en los laterales para constituir sendas torres esquineras. La portada es adintelada, con moldurajes clásicos y en el dintel se superponen las fechas de 1592, que alude a la finalización de la portada, y la de 1946 que debe corresponder a la reparación sufrida tras la guerra civil. Sigue encima un paño de sillería y justo debajo del balcón de forja corre el lema de la familia: DEXTE(RA) DOMINI FECIT VIRTUTEM / DEXTERA DOMINI EXALTAVIT ME. El balcón luce un recercado de piedra moldurada, sencilla cornisa y florón de remate. A su lado, blasonan la fachada sendos escudos heráldicos enormes, con yelmos plumeados, máscaras y encintados manieristas de cueros enrollados acogiendo las armas de los Fernández de Córdoba y alianzas; en el escudo de la izquierda se puede ver el mismo lema de debajo del balcón. En las esquinas destacan las consabidas torres de triple arquería de ladrillo a cada lado sobre pilares ochavados. En el interior se distinguen unas buenas armaduras de limas apeinazadas. Sus tejados, con cumbreras de cerámica vidriada, rematan en jarras de cerámica donde engastan las cruces y veletas.
