Este Palacio tiene su origen en el siglo XVII estando situada entre a Plaza de Santo Domingo y la calle Trapería, correspondiendo en sus inicios a las antiguas casas de los Santa Cruz y de los Lucas, que se construyeron adosadas a las murallas árabes junto a la Puerta del Mercado de las mismas. La que daba acceso desde Trapería al espacio extramuros a la antigua Plaza del Mercado, como se le llamaba entonces a la actual Plaza de Santo Domingo, mercado que abarcaba toda la plaza y llegaba hasta detrás del Romea e incluso la calle del Arco de la Aurora.
Su estilo arquitectónico es manierista teniendo elementos con un aspecto muy recargado, que ya van prefigurando las características usuales del Barroco.
Con el transcurrir de los años se vinculo su titulación con los apellidos Almodóvar y Melgarejo.
En este portal barroco del Palacio del siglo XVII que fue reformado en 1908 se puede apreciar las figuras de los gigantes o tenantes, con que se distinguían en la época las casas de los personajes pertenecientes a la alta sociedad que tenían por objeto atemorizar a los ladrones ante la magnificencia de sus moradores.
Durante un largo periodo de tiempo fue sede del Gobierno Civil de la provincia hasta 1950.
Al ser los marqueses miembros de la Cofradía del Rosario mandaron construir una Capilla anexa al Convento de Santo Domingo, dedicada a la citada Virgen al otro lado de la calle y dotándola de un arco que la uniera con su Palacio. El arco fue edificado por el arquitecto Toribio Martínez de la Vega y que dió origen al célebre y celebrado actual Arco de Santo Domingo que une la citada plaza con la de Romea.