Fue el deán Ortega un hombre culto de total confianza del secretario don Francisco de los Cobos, siendo nombrado por este prohombre capellán mayor de la Sacra Capilla de El Salvador, cuyo proceso edilicio siguió de cerca. Construido en piedra de cantería, hacia mediados del siglo XVI ya debía estar en gran parte construido.

Pocas son las referencias documentales sobre su proceso constructivo, pero V. M. Ruiz Fuentes ha publicado algunos datos de gran interés al respecto. El 31 de octubre de 1550 el carpintero Diego de Ocón se obligaba a labrar diversas piezas de carpintería: ventanas altas y bajas de la fachada, puertas interiores, cubiertas de los corredores y cuartos altos. Las directrices para todas estas obras fueron dictadas por el arquitecto real Luis de Vega, relacionado con las obras de los palacios de Úbeda y Valladolid, mandados construir por Francisco de los Cobos.

En la misma fecha, el cantero Martín de Mendiola se comprometía a enlosar el patio principal, entre otras actuaciones, bajo la supervisión de Andrés de Vandelvira. En 1553 se proyectaron las obras de la fachada Oeste, siendo el cantero Pero Jorge el encargado de proporcionar la piedra, determinándose que tanto el friso, como la cornisa y las molduras de las ventanas serían iguales a las de la fachada principal, aunque en realidad difieren. La escasa documentación sobre la relación de Andrés de Vandelvira con las obras de este palacio no impide vincularlo con su proceso edilicio.

Los elementos compositivos forman parte del léxico arquitectónico empleado por Andrés de Vandelvira, si bien se advierten ciertas particularidades. El edificio, de planta rectangular, está conformado por una gran fachada principal de proporciones apaisadas y dos laterales, con dos alturas y sótano. Los estilemas de Vandelvira se aprecian claramente en las ventanas esquinadas con columnilla marmórea, empleadas por él en el palacio Vela Cobos o en el del Conde de Guadiana; en los frontones triangulares con espejo en su tímpano; amén de las diversas composiciones de ventanas, balcones y cornisamento, con abultado trabajo de ovas y dardos, similar al empleado en el edificio de la Casa del Corregidor y Cárcel Real de Baeza, inscrito tradicionalmente también en el catálogo vandelviriano.

Pieza esencial dentro del conjunto es el patio, uno de los más bellos y elegantes de Andalucía, con cuatro galerías en sus dos pandas, con arcos medio punto apeados en elegantes y finas columnas de mármol blanco de orden dórico, en las enjutas espejos. Vandelvira utiliza en este palacio estilemas sacados de Sebastián Serlio (cornisa, portada lateral de la fachada esté conservada en su traza original, etc.), y en general del lenguaje clasicista, pero también se mantiene fiel a la tradición en la fina y grácil composición del patio, acomodado a lo que se ha venido en llamar el “módulo andaluz”, consecuencia de los finos soportes del arte nazarita, empleado en esta misma ciudad en los patios de la Casa de las Torres y en el palacio de Vázquez de Molina, actual Ayuntamiento.