Le origini del Palazzo del Priorato, situato nella cittadina di Gatchina, vicino a San Pietroburgo, sono legate alla storia dell’Ordine di Malta, uno dei più antichi ordini cavallereschi della Chiesa Cattolica Romana, che subì persecuzioni dopo la Rivoluzione francese.
Paolo I era il patrono dei Cavalieri di Malta, e per questo venne richiesto il suo appoggio. Lo zar offrì il suo aiuto e nel gennaio del 1797 firmò una convenzione sul Gran Priorato dell’Ordine di Malta, da istituire sul territorio russo. Nel novembre 1798, Paolo I fu insignito del titolo di Gran Maestro.
L'Imperatore consegnò quindi il Palazzo Vorontsov di San Pietroburgo ai vertici dell'Ordine di Malta e decise di costruire una residenza estiva per il Principe Conde, Priore dell'Ordine, a Gatchina, dove lo stesso Paolo I possedeva già un palazzo.
Il Principe Conde non arrivò mai a San Pietroburgo, ma quando la costruzione fu terminata Paolo I, in qualità di Gran Maestro, si ritrovò a essere uno dei capi dell'Ordine di Malta. Da lì nacque la leggenda, secondo la quale esisterebbe un passaggio sotterraneo che collegherebbe il Palazzo Gatchina al Palazzo del Priorato.
Il Palazzo del Priorato è stato progettato dall'architetto e ingegnere Nikolaj Lvov, che ha supervisionato anche i lavori di costruzione. Lvov realizzò numerosi palazzi neoclassici e alcune chiese non solo a San Pietroburgo, ma anche a Mosca, Torzhok e dintorni.
Per costruire il palazzo, Lvov mise a punto una nuova tecnologia, utilizzando della terra come materiale. In precedenza, il terreno pressato era stato utilizzato per innalzare fortificazioni, ma Lvov sviluppò una tecnologia particolare che permise di realizzare un intero castello di terra, perfino su un terreno paludoso!
Il Palazzo del Priorato è infatti l'unico edificio in terra battuta “sopravvissuto” in Russia. E gli esperimenti del progettista furono sostenuti dallo zar, che nel 1797 emise un decreto per innalzare un’istituzione scolastica in terra battuta.
Il figlio di Paolo I, Alessandro I, trasferì il palazzo al Tesoro di Stato; per un breve periodo ospitò una chiesa luterana, anche se per la maggior parte del tempo l’edificio rimase inutilizzato.
Un secolo più tardi, il palazzo fu interamente ristrutturato ed equipaggiato con sistemi di approvvigionamento idrico e fognario, per renderlo abitabile durante tutto l'anno, quindi fu trasformato in appartamenti per i cortigiani. All'inizio del XX secolo il Palazzo del Priorato fu trasformato in un luogo d'arte e utilizzato per allestire varie mostre.
Durante la Prima guerra mondiale l’edificio ospitava un ospedale militare, e vi furono diversi tentativi di farlo saltare in aria da parte dei nazisti durante la Seconda guerra mondiale. Ma la tecnica di costruzione di Lvov si rivelò di una qualità tale che le mura del palazzo resistettero all'esplosione, che danneggiò solo parzialmente il tetto. Il palazzo è stato restaurato solo negli anni '80.
Il Palazzo del Priorato e il parco circostante hanno sempre affascinato gli artisti: nel corso degli anni sono apparsi moltissimi quadri, disegni e incisioni che raffigurano questo luogo. Nella Galleria Tretyakov, ad esempio, è esposto un paesaggio di Andrej Martynov con il lago in primo piano e il palazzo sullo sfondo.
Nel XX secolo, il Palazzo del Priorato e il parco hanno ispirato gli artisti Nikolaj Lansere, Mstislav Dobuzhinskij e Alexandre Benois.
Il Palazzo del Priorato ha ricevuto lo status di museo solo nel 2002 e dal 2004 ospita delle mostre. La cappella del palazzo ha un'acustica eccellente e viene utilizzata come sala da concerto. Si dice che nel giorno dell’inaugurazione, uno degli orologi risalenti al XVIII secolo, fermo da tempo, abbia ripreso improvvisamente a funzionare.