La costruzione fu avviata nel 1458 da Lorenzo de Roxis sul luogo del precedente palazzo podestarile, ormai in rovina. Stando alle cronache, l'edificio crollò subito a causa di mattoni malcotti e nel 1459 un nuovo palazzo fu iniziato da Matteo di Recevudo, zio di Melozzo degli Ambrogi, che concluse la costruzione nel 1462. L'edificio, realizzato interamente in cotto, presenta un portico con archi a sesto acuto - gli unici a sopravvivere fino ai nostri giorni a Forlì - elementi ancora gotici che documentano a quelle date un mancato aggiornamento architettonico. In un capitello e in un pilastro del portico è scolpito lo stemma (su campo dorato tre bande verdi da cui si erge un leone rampante) della famiglia Ordelaffi, che tenne la signoria della città dalla fine del XIII secolo fino al 1480. Il palazzo fu trasformato durante il restauro del 1921-1924 quando fu aggiunto un balconcino nel punto in cui si trovava la gabbia di ferro per esporre i condannati alla pubblica derisione.