La costruzione del palazzo, adornato di preziosi azulejos in stile mudejar e di giardini fu iniziata nel 1493[1] da Pedro Enriquez de Quiñones (Adelantado di Andalusia) e da sua moglie Catalina de Rivera, fondatori della Casa de Alcalá. In seguito l'edificio fu completato da Fadrique Enriquez de Ribera (primo marchese di Tarifa), e proprio per un suo pellegrinaggio nel 1519 a Gerusalemme[1] il palazzo porta l'attuale nome. Al suo ritorno, la tradizione dice che il marchese scoprì che la distanza tra la sua abitazione e la chiesa collocata fuori dalle mura, conosciuta come la Croce del campo era uguale a quella tra le rovine della residenza di Ponzio Pilato e il Calvario. Sorpreso da questa coincidenza, il marchese stabilì lungo il percorso le quattordici stazioni della Via Crucis, di cui la prima, la sua casa, corrispondeva alla Casa di Pilato. Questo fu il motivo per cui si è creduto che fosse una copia della casa di Pilato, infatti le stanze vennero denominate con nomi relativi alla Passione di Cristo: come per esempio il "Salone del Pretorio" e "Cappella della Flagellazione".
Pure gli interni sono notevoli, decorati ad azulejos[1] e formati da grandi saloni con soffitti decorati, come nel salon dorado. Una scala porta al piano superiore, coperto da una cupola in legno mudejar.[1] Sono presenti inoltre anche affreschi della galleria e della sala dei vetri risalenti al 1539, in cui sono raffigurati i temi della natura e dell'antichità.
Nel palazzo trova posto anche una cappella, ornata da decorazioni in stile gotico-mudejar.[1]