L'architetto scozzese Charles Cameron lavorò in Russia circa trent'anni, su invitato personale dell'Imperatrice Caterina II, e questo Palazzo di Paolo viene valutata come la sua opera maggiore, tra le più importanti dell'architettura del classicismo russo. Il palazzo è situato in un luogo veramente suggestivo, circondato da un grande parco pittoresco che supera i 600 ettari sul fiume Slavjanka.
Cameron, che in Russia veniva affettuosamente chiamato Carl Carlovich, era un ammiratore dell'architettura classica e di Palladio e conferì a questa fabbrica la forma della villa palladiana. L'ampliamento del palazzo venne affidato all'architetto italiano Vincenzo Brenna con le costruzioni aggiunte alle ali laterali.
Subì numerosi ricostuzioni a seguito di incendi nel 1830 e da incursioni militare in conseguenza dell'occupazione dell'allora Leningrado da parte di Hitler.