Le fondamenta del palazzo risalgono quasi allo stesso tempo di quelle dell’attuale Basilica di San Pietro.
Fu il Cardinale Francesco Armellini ad iniziare la costruzione dell’edificio nel 1517. I lavori furono terminati nel 1520. Per più di 40 anni il palazzo rimase di proprietà della famiglia Armellini per poi essere venduto nel 1565 alla famiglia Cesi.
I Cesi, di origine umbra, in pochissimi anni divennero una delle famiglie emergenti di Roma, grazie a Pietro, senatore di Roma e ai tre cardinali che tra il ‘500 e ‘600 aumentarono il prestigio della famiglia, quali Paolo, Federico e Pietro Donato. Quest’ultimo si trasferì a Roma per assistere il Papa in varie funzioni diplomatiche, e nel 1570 fu nominato cardinale. Egli fece ristrutturare completamente palazzo affidando il compito ad un architetto lombardo, Martino Longhi “il Vecchio” che inglobò, risparmiando tempo e denaro, il preesistente edificio creato per gli Armellini forse con architettura di Antonio da Sangallo il Giovane.