A construção do palácio foi encomendada em 1744 pela imperatrizrussaElizaveta Petrovna, tendo sido desenhado por Bartolomeo Rastrelli, o mais famoso arquitecto em actividade no Império Russo naquela época. Um dos alunos de Rastrelli, Ivan Michurin, juntamente com um grupo de outros arquitectos, completou o palácio em 1752. No entanto, a Imperatriz Elizaveta não viveu tempo suficiente para ver o palácio concluido. A primeira figura real a permanecer no edifício foi a Imperatriz Catarina II da Rússia, a qual visitou Kiev em 1787. No final do século XVIII e no início do século XIX o palácio foi a residência principal dos Governadores-Gerais da Guberniya (província do Império Russo).
No início do século XIX, o palácio ardeu numa série de incêndios. Cerca de meio século depois, em 1870, Alexandre II da Rússia teve o palácio reconstruido pelo arquitecto Konstantin Mayevsky, usando antigos desenhos e aguarelas como guia. Foi então rebaptizado em homenagem à Imperatriz reinante Maria Alexandrovna. De acordo com os seus desejos, foi instalado um grande parque no lado sul do palácio. O Palácio Mariyinsky foi usado como residência para as visitas de membros da família imperial até 1917.
Durante os anos da Guerra Civil Russa, entre 1917 e 1920, o palácio foi usado como quartel-general militar. Na década de 1920 o edifício pertenceu a uma escola agrícola, tendo-se tornado num museu pouco tempo depois. O Palácio Mariyinsky foi severamente danificado durante a Segunda Guerra Mundial, tendo sido restaurado no final da década de 1940. Outras importantes obras de restauro foram concluídas no início da década de 1980.