Visual landmarks are defined as objects with prominent shape or size that distinguish themselves from the background. With the help of landmarks, animals can orient themselves in their natural environment. Yet, the way in which landmarks are perceived and encoded has previously only been described in insects, fish, birds, reptiles and terrestrial mammals. The present study aimed to provide insight into how a marine mammal, the harbour seal, encodes goals relative to landmarks. In our expansion test, three harbour seals were trained to find a goal inside an array of landmarks. After diagonal, horizontal or vertical expansion of the landmark array, the search behaviour displayed by the animals was documented and analyzed regarding the underlying encoding strategy. The harbour seals mainly encoded directional vector information from landmarks and did neither search arbitrarily around a landmark nor used a rule-based approach. Depending on the number of landmarks available within the array, the search behaviour of some harbor seals changed, indicating flexibility in landmark-based search. Our results present the first insight into how a semi-aquatic predator could encode landmark information when swimming along the coastline in search of a goal location.