Su progetto di Matteo Carnelivari - il maggior architetto del tempo - lo splendido palazzo fu fatto edificare, intorno al 1490, da Guglielmo Aiutamicristo barone di Misilmeri e di Calatafimi. Lo stile è gotico-catalano, con evidenti influssi rinascimentali. Notevoli sono il portale d’ingresso e il duplice loggiato che prospetta sul cortile interno. Il progetto iniziale prevedeva una struttura grandiosa, che però fu realizzata solo in parte. L’impegno si dimostrò eccessivo, anche per il barone, banchiere di origine pisana, che pur disponeva di larghi mezzi. In ogni modo, ne uscì un palazzo di grande pregio architettonico, che - superbamente arredato all’interno - non tardò a richiamare ospiti illustri.
Nei primi anni del Cinquecento vi albergò la regina Giovanna, moglie del re Don Ferrante di Napoli; nel 1535 vi fu ricevuto l’imperatore Carlo V, che preferì Palazzo Aiutamicristo al palazzo reale, ritenuto non consono alla imperiale magnificenza; nel 1544 vi prese alloggio Muley Hassan, re di Tunisi, poco prima di essere accecato dal figlio Ajaja; nel 1576 vi fu accolto Don Giovanni d’Austria, fratello del re Filippo II, vincitore della battaglia di Lepanto.
Nel 1588 Margherita Aiutamicristo concesse in affitto il palazzo a Francesco Moncada, primo principe di Paternò, che presto chiederà, ed otterrà, di tramutare l’affitto in proprietà.