Se encuentra en la parte alta de la cuesta del Bailío, a la que da nombre y cuyo origen se remonta al reparto que realizó Fernando III tras la expulsión de los musulmanes, recayendo la propiedad de la misma en familia de los Fernández de Córdoba, señores de Aguilar.
Durante la primera mitad del siglo XVI vivió en ella Pedro Núñez de Herrera, gran bailío de Lora de la Orden de San Juan e hijo natural de Alfonso de Aguilar, que murió en África en 1578 con el rey don Sebastián, cuyo cargo dio nombre a la casa.
Los Marqueses de Almunia heredaron el palacio y vendieron en 1710 una parte al obispado de Córdoba para que edificara el hospital de San Jacinto y la iglesia de Ntr.
En la actualidad sus dependencias se reparten entre la Biblioteca Viva de al-Ándalus y el hotel Palacio del Bailío.
La portada tardogótica del palacio está atribuida a Hernán Ruiz II y en ella destaca la decoración plateresca del tímpano.