Antigamente uma propriedade da chancelaria sueca, Strelna foi escolhida por Pedro, o Grande como lugar para a sua futura residência de Verão, em 1714. Jean Baptiste Le Blond (1679-1719), famoso pelo seu trabalho com André Le Nôtre no Château de Versailles, foi contratado para preparar desenhos para o que deveria ser um palácio e parque. Le Blond encarava o palácio como um Chateau d'Eau (Castelo de Água), situado numa ilha redonda. Os jardins foram executados segundo o desenho de Le Blond, mas a morte do mestre impediu-o de completar um projecto mais elaborado para o palácio.
Em 1718, foi construído um palácio temporário de madeira em Strelna. Este seria usado pela realeza russa como uma espécie de pavilhão de caça, sendo, felizmente, preservado até à actualidade. Depois da morte de Le Blond, o encargo de construir o grande palácio passou para Nicholo Michetti, um discípulo do grande Carlo Fontana. Uma pedra angular foi colocada em Junho de 1720, mas no próximo ano tornou-se evidente que o lugar estava em más condições para a instalação de fontes, razão pela qual Pedro I decidiu concentrar a atenção para o vizinho Peterhof. Desapontado, Michetti deixou a Rússia, e todos os trabalhos em Strelna foram suspensos.
Ao subir ao trono, em 1741, a filha de Pedro I, Isabel, teve a intenção de terminar o projecto do seu pai. O seu arquitecto favorito, Bartolomeo Rastrelli, foi convidado a expandir o desenho de Michetti. No entanto, a atenção de Rastrelli rapidamente foi distraída por outros palácios, tanto no Peterhof como em Tsarskoye Selo. Por esse motivo, o palácio de Strelna ficou incompleto até ao final do século.
Depois de 1917, o palácio entrou em decadência: foi entregue a uma comuna de trabalho infantil, e depois a uma escola secundária. Por um período durante a Segunda Guerra Mundial, os alemães ocuparam Strelna e tiveram ali uma base naval. Foram trazidos da Itália alguns homens da Decima Flottiglia MAS e barcos de ataque, os quais montaram base em Strelna. O Comando Russo de Homens-rãs atacou esta base e destruiu esses barcos.
Depois da devastação causada pela ocupação germânica, apenas as paredes do palácio permaneceram erguidas. Toda a decoração do interior tinha desaparecido.
O palácio reconstruído
Até 2001 não foi empreendido qualquer restauro efectivo. Nesse ano, Vladimir Putin ordenou que o palácio fosse convertido numa residência presidencial em São Petersburgo. O parque, com canais, fontes e pontes levadiças, foi então recriado segundo os desenhos originais de Le Blond e completado com um pavilhão ligado à água pela costa marinha. Em frente ao palácio ergue-se a estátua equestre de Pedro, o Grande, instalada originalmente em Riga no ano de 1911, enquanto que a escultura modernista de Mikhail Shemyakin, representando a família desse Czar a deambular pelo jardim, pode ser encontrada próximo da margem.
O renovado Palácio de Constantino acolheu mais de cinquenta chefes de estado durante as celebrações do tricentenário de São Petersburgo, em 2003. Três anos depois, entre 15 e 17 de Julho de 2006, recebeu a 32ª cimeira do G8. Durante essa cimeira, os líderes do mundo ficaram acomodados em oito luxuosos bangalós à beira-mar. Cada um desses edifícios foi baptizado em homenagem a uma cidade histórica da Rússia. Os estábulos do início do século XIX foram reconstruídos e adaptados como um hotel de quatro estrelas para outros visitantes.
O facto de o luxuoso palácio acolher recepções e reuniões oficiais não significa que esteja encerrado ao público. No seu interior encontram-se expostas três colecções: a colecção de heráldica do Museu do Ermitage, uma exposição sobre os quatro príncipes que possuíram o palácio (três dos quais se chamavam Constantino, vindo daí o seu nome actual) e uma exposição pertencente ao Museu Marítimo.
Outros marcos
Na vizinhança do Palácio de Constantino podem ser vistas várias outras residências Romanov, nomeadamente as pertencentes aos ramos Nikolaevichi e Mikhailovichi da família.
Entre as outras referências existentes em Strelna incluem-se a casa de campo de Mathilde Kschessinska e um mosteiro em ruínas, com numerosas igrejas desenhadas por Luigi Rusca. O mosteiro merece destaque por ser local de sepultura dos irmãos Zubov e de outros nobres russos. O chanceler imperial Alexander Gorchakov também foi ali enterrado em 1883.