L'edificio in cui si sviluppa il museo ha raggiunto la struttura attuale a seguito di trasformazioni e modifiche che si sono susseguite nei secoli. Il nucleo centrale appartiene infatti al medievale Palazzo della Residenza o dei Conservatori del Popolo che governarono la città fino alla presa da parte dei Malatesta nel 1371.

I signori di Rimini ressero il potere fino al 1430 e, nel corso di quegli anni, il Palazzo venne trasformato nella loro abitazione privata. In seguito, l'edificio venne ampliato fino a inglobare l'antico Monte Pio, uno dei primi monti di pietà, e ad assumere pressoché la struttura attuale intorno al 1456 quando in particolare fu ridefinita la sala dei Conservatori, dove si trova la Resurrezione di Piero della Francesca. L'Arco della Pesa, sovrastato dall'affascinante terrazza del Museo che domina l'ingresso al centro cittadino, collegava l'antico Palazzo della Residenza all'adiacente Palazzo del Capitano, o Pretorio, che risale al XIV secolo.