Il Palazzo di Caterina di Mosca, (da non confondere con il Palazzo di Caterina di Carskoe Selo) commissionato da Caterina II, nella sua forma attuale, fu costruito in varie fasi fra il 1773 ed il 1797. Il primo progetto è attribuito ad Antonio Rinaldi, ma in seguito fu rimaneggiato dagli architetti Karl Blank, Francesco Camporesi e Giacomo Quarenghi.
Il complesso è anche conosciuto come il Palazzo Golovin, dal nome del suo primo proprietario, il conte Fyodor Golovin, il primo cancelliere dell'Impero russo. Dopo la sua morte l'imperatrice Anna I di Russia commissionò all'architetto italiano Bartolomeo Rastrelli di costruire il Palazzo con una residenza in stile barocco che fu in seguito chiamata Annenhof. La residenza di Lefortovo, che era la preferita di Anna, era costituita da due edifici a due piani in legno, il Palazzo d'Estate e il Palazzo d'Inverno.
Annenhof fu abbandonato dopo un incendio nel 1746. Caterina II che trovava entrambi gli edifici, oltre che fuori moda, fatiscenti ne ordinò la demolizione nel 1760. In una prima fase fu incaricato della progettazione Antonio Rinaldi. I lavori, iniziati verso il 1773, dal 1778 furono diretti da Karl Blank, nel 1783 da Francesco Camporesi,, che pare abbia curato in particolare modo alcune parti decorative, come quelle in stucco, ed infine dall'inizio degli anni 1790 da Giacomo Quarenghi e furono conclusi nel 1797.