El proyecto del palacio lo realiza Andrés de Vandelvira (existe constancia por contrato firmado en el palacio). Existen, en Úbeda, cuatro edificios más de los que se tenga certitud de intervención de Vandelvira: la Sacra Capilla del Salvador, el Hospital de Santiago, palacio del Marqués de la Rambla y el Palacio Vázquez de Molina.
Las obras del palacio las lleva a cabo el maestro de cantería Jorge Leal. El Palacio se construye en dos fases: a partir de 1551, se levantan las dos primeras plantas; diez años más tarde, en 1561, se completa con la galería de la última planta (terrao), finalizando esta obra en 1563.
Andrés de Vandelvira fue hijo y discípulo del también arquitecto, Pedro de Vandelvira, y estaba casado con Luisa de Luna, de Villacarrillo, con la que tuvo siete hijos, uno de los cuales, Alonso de Vandelvira, escribió un libro Libro de cortes de piedra, que ayudó a que fuera conocida la obra de su padre. Fundó una capellanía, en la Iglesia Parroquial de Villacarrillo, a favor de su hijo el presbítero y licenciado Pedro de Vandelvira. Siendo en este último lugar donde acopió la mayor parte de su patrimonio.
Con 21 años también aparece Vandelvira en unas ambiciosas obras del Convento de Uclés, obra iniciada por Francisco de Luna en 1529; su participación, “a la sombra de la escuela plateresca toledana”, es uno de los ingredientes formativos de su personalidad.
Instruido por su padre, que había estudiado en Italia, fue un varón de gran cultura; conocía los tratados más famosos de la época, y los puso en práctica gracias a los mecenas que encontró, principalmente en la provincia de Jaén, como la misma iglesia, y los nobles relacionados con la familia Molina, como Francisco de los Cobos y Molina, protector de su padre. Fue el inventor de la bóveda vaída y de otras ingeniosas soluciones constructivas.
Realizó la construcción de la impresionante Plaza Mayor de su localidad natal, Alcaraz, así como numerosas construcciones civiles y religiosas alrededor de ésta.
Entre sus obras más notables está la Sacra Capilla del Salvador, realizada en Úbeda sobre un proyecto inicial de Diego de Siloé, por encargo de Francisco de los Cobos. Tras esta obra, vienen muchas otras, como la capilla de los Benavides en el convento de San Francisco de Baeza, una obra maestra (por desgracia perdida en parte tras el terremoto de 1755); la intervención en la catedral de Baeza o en el Antiguo Convento de Santo Domingo de La Guardia de Jaén, el Hospital de Santiago de Úbeda, el Palacio Vela de los Cobos o la mismísima Catedral de Jaén, obra también iniciada por su padre, Pedro de Vandelvira en 1540, donde ejecutó las obras que su padre había trazado, especialmente la fachada de mediodía, la sala capitular, el panteón, la sacristía y las capillas del lado de la epístola.
También trazó y dirigió la iglesia de Nuestra Señora de la Asunción de Villacarrillo, que es de tres naves divididas por cinco columnas corintias por banda y el retablo mayor y colaterales y fue una de sus primeras y grandes obras en la provincia de Jaén. También se le atribuye la traza de la nave central de la Iglesia de La Asunción en Jódar.
Se le atribuye la torre del Tardón en Alcaraz, que guarda muchas similitudes en su decoración con la Capilla del Salvador de Úbeda.
Una de sus últimas obras, en las que muestra una gran pureza de estilo es el Hospital de Santiago, en Úbeda. A su muerte, su cuerpo fue enterrado en la Basílica de San Ildefonso de Jaén.
