Port Hedland is known by the Indigenous Kariyarra and Nyamal people as Marapikurrinya, which either means "place of good water" (as told by a Nyamal language speaker) and makes reference to the three reliable fresh water soaks that can still be seen in and around the town, or as the town council's website says "refers to the hand like formation of the tidal creeks coming off the harbour (marra - hand, pikurri - pointing straight and nya - a place name marker)". According to Dreamtime legend there was a huge blind water snake living in the landlocked area of water known as Jalkawarrinya. This landlocked area is now the turning basin for the ships that enter the port and as the story goes, "the coming of the big ships meant it was unable to stay".
Though the coastline in the area had been explored in the 18th century, Captain Peter Hedland was one of the first Europeans to explore the harbour for the purpose of developing an export port. Peter Hedland arrived in the area in April 1863 onboard his boat, Mystery that he had built himself at Point Walter on the banks of the Swan River. He named the harbour Mangrove Harbour and reported that it would make a good landing site with a well protected harbour and that there was also fresh water available. What Hedland failed to point out was that the harbour was difficult to enter because of a huge sandbar that sealed the entrance meaning it was only accessible at high tide and that it was difficult to enter in bad weather because of the narrow entrance.
In 1866, the resident Magistrate of Roebourne, Treverton Sholl, commissioned Charles Wedge to investigate alternative town sites to Roebourne. Wedge's reports were pessimistic about the suitability of Port Hedland. In 1891, exploration of the area by Tom Traine, John Wedge and Syd Hedley identified two landings and described the harbour as "pretty as well as safe". In September 1895, Cossack residents requested the District Surveyor to survey the headland at
