William Barents was the first to explore Magdalenefjorden in 1596. Here he found walrus tusks, which caused him to name the fjord Tusk Bay. The English explorer and whaler Robert Fotherby entered the fjord in 1614, claiming it for King James I of England and naming it Maudlen Sound, and the small, sheltered bay on its southern shore Trinity Harbor. The English subsequently established a whaling station in Trinity Harbor, on what is now called Gravneset. It was later taken over by the Dutch. The remains of four blubber ovens or furnaces have been found on Gravneset, as well as a graveyard containing about 130 graves dating from the 17th to the late 18th century.
The Dutchman Joris Carolus was the first to label the fjord Mari mag. bay. Abraham Goos called it Magdalenen sond, and Guljelmus Cæsius S. Maria Magdalene sond.