Het Maria Hendrikapark maakt deel uit van de oude stadsvestingen van Oostende. Na de beslissing in 1865 om de vestigingen af te breken, werd de Duitse landschapsarchitect Eduard Keilig door Koning Leopold II de opdracht  gegeven plannen te maken tot aanleg van een park.

Bij de officiële opening in juli 1892 kreeg het park de naam Maria Hendrikapark of “Parc Marie Henriette”.  Lokaal was het park meer gekend onder de naam “Bois de Boulogne” of kortweg “het Bosje”. In die tijd was op het eiland reeds een drankgelegenheid gebouwd genaamd “La Laiterie Royale”.

Nog steeds onder impuls van Koning Leopold II werden er al nieuwe uitbreidingsplannen voor het park opgemaakt die reeds in 1898 uitgevoerd werden.  De toenmalige Koning had een voorliefde voor Oostende en bouwde in zijn geliefkoosde stad heel wat mooie bouwwerken .  

Aan het einde van zijn leven besloot Koning Leopold II om zijn verworven eigendommen aan het land te schenken. Het Maria Hendrikapark maakt deel uit van de Koninklijke Schenking.
Hieraan was de voorwaarde gekoppeld dat de oorspronkelijke functie en uitzicht diende te worden bewaard.

Het is begrijpelijk welk mooi groen zicht Koning Leopold II aan de binnen sporende toerist wilde geven. 

Het duurde tot 1967 wanneer op het eiland het Laiterietje werd afgebroken en een nieuw gebouw opgericht. Dit nieuwe gebouw kreeg de naam "Koninginnehof".

Wanneer er in 2003 in het park grondige werken aan de grote vijver werden uitgevoerd,  diende het waterpeil van de vijver zo ver mogelijk te worden gedaald om de oeverwerken toe te laten. Na vele jaren kwam er voor de eerste maal een stuk van die geschiedenis in de vijver terug zichtbaar.
Aan de oevers kwamen de oude versterkingen van de stadsvestingen bloot te liggen. Op vele plaatsen kon men de vormen van het oude park en de vestingen terug vinden. Zo werd de oude spoorwegbedding zichtbaar waar vroeger de trein de stad binnen reed. Het oude treinstation van Oostende was destijds namelijk gelegen op de plaats waar het grootwarenhuis Delhaize nu is.