The history of Maputo, the capital of Mozambique, traces its origins back over 500 years, when a fishing village developed by Maputo Bay on the site where the modern city of Maputo now stands. The first Europeans to discover the bay were Portuguese navigators led by António de Campo in 1502. In 1544, the Portuguese merchant and explorer Lourenço Marques reached the bay and named it Delagoa Bay. The Portuguese established a fort on the site, but were soon forced to abandon it. In 1721, the Dutch East India Company established Fort Lydsaamheid on the bay, but abandoned it due to conflicts with local Africans and the unhealthy environment. In the mid-18th century, the Portuguese returned to the bay, selling ivory to British ships carrying Indian textiles. In 1773, William Bolts of the Trieste Company reached the bay and claimed it for the Holy Roman Empire. Bolts and the Austrians were forced out in 1781 by Portuguese ships sent from Goa.

That year, hoping to prevent other European powers from claiming the area in the future, the Portuguese constructed a fortress on the bay, naming it Lourenço Marques. During the late 18th and early 19th century, the fort was mainly used by French, British, and American whaling ships to stop for provisions. A town grew around the fort starting around 1850, and in 1877, it was elevated to city status. In 1898, the colony of Portuguese Mozambique relocated its capital there. In the late 19th and early 20th centuries, Lourenço Marques grew both in population and economic development as a port city. Upon Mozambican independence in 1975, the city became the national capital and was renamed Maputo. During the Mozambican Civil War, the city's economy was devastated. When the war ended, the FRELIMO government launched a program to revive the city's economy, and to clean up the city by forcibly removing criminals, squatters, and undocumented residents. Since then, Maputo's economy, centered around its port, has recovered, and stability has returned.

The first inhabitants of the region surrounding what is now known as Maputo Bay were likely Khoisan peoples. Around 700 years ago, Ronga-speaking Bantus migrated from the north and settled around the area. By the 1500s, the site that Maputo now occupies had developed into a small fishing village.

The first Europeans to reach the bay were Portuguese seamen under the command of António de Campo, one of Vasco da Gama's captains, in 1502. In 1544, the Portuguese merchant trader and explorer Lourenço Marques, along with António Caldeira, was sent by the Governor of Mozambique Island on a voyage of exploration. Marques visited the bay, and navigated the upper reaches of the estuaries feeding into it. Marques named the bay Baía da Lagoa (Portuguese: "Bay of the Lagoon"), which was anglicized to Delagoa Bay. King John III of Portugal declared the bay Baía de Lourenço Marques in his honor, but this name was never used commonly outside of Portugal. In the late 16th century or 17th century, the Portuguese established La Goa, a fort and trading post, on the site. The fort, manned by a single Catholic friar and several merchants, was a small-scale but profitable enterprise. However, ultimately the multitudes of mosquitos that swarmed the area forced the Portuguese to abandon the fort.

On 29 March 1720, three Dutch ships, the Kaap, the Gouda, and the Zeelandia, reached the bay. The Dutch navigators, led by Johannes Steffler, were warmly welcomed by the local Batonga tribe and its chief, Mpfumu. In March 1721, the Dutch East India Company purchased the land around the bay from Mpfumu and set about reconstructing the old Portuguese fort, which had fallen into ruin. The repaired fort was named Fort Lydsaamheid (Dutch: "Fort Endurance"). Within three weeks of their arrival 100 of the original sailors, craftsmen, and soldiers had died of fever. In August 1720, 80 new arrivals came to replace them. Beginning in April 1721, it was governed by an opperhoofd as a dependency of the Dutch Cape Colony. From April to 28 August 1722, when the Dutch recaptured it, the fort was occupied by pirates led by John Taylor.

Fort Lydsaamheid's trade mainly centered around the trade of ivory, and to a lesser extent, slaves, tin, aloes, gold dust, ambergris, honey, copper, and rice. During the fort's nine years of operation, it exported 22,500 kg (49,574 lb) of ivory, and 288 slaves. The slave trade, while at its global peak, was minimal, because Dutch slave traders preferred to go to northern ports, where slaves could be more easily obtained, instead of Lydsaamheid, which was not equipped to handle large quantities. The settlers at the fort tried to farm, but all attempts ended in failure.

In addition to trading, the fort was used as the starting point for several expeditions into the Mozambican interior in search of reputed gold mines in Monomatapa, which the Dutch believed was the gold-producing region mentioned as Ophir in the Bible. The first such expedition, led by Steffler, was forced to turn back after they were attacked by natives in the Lebombo Mountains. Another expedition, this time led by Johannes Monna in the late 1720s, set forth with native guides, but after failed trading attempts and a skirmish with a tribe armed with spears, also turned back. They returned to find Fort Lydsaamheid in a state of disorder following the discovery of a mutiny plot. The 62 would-be mutineers, who were disgruntled with the fort's terrible conditions, were arrested, tortured, and killed after their plans were discovered. Of the 62, 22 had been beaten with iron bars and their heads severed, others suffocated and beheaded, and the remainder simply hanged. In addition, in 1728, 28 Dutch soldiers abandoned Lydsaamheid and trekked to Inhambane, where the eighteen who survived the journey told the Portuguese there of the mistreatment and diseases they had experienced at the fort.

Throughout its existence, Fort Lydsaamheid suffered from meager trade, an unhealthy environment, and general discord, and had failed to find the fabled gold-producing region. In 1729, Cape Colony officials received orders from Heeren XVII, the Dutch East India Company's board of directors, to abandon the fort. Instead of immediately implementing these orders, the colony offered a one-year grace period to the fort's personnel. However, during this period, the fort's men, under the leadership of Jan van de Capelle, attacked Chief Mafumbo, whose tribe had settled too close for comfort. In a battle that followed, several local chiefs attacked, killing all the Dutch soldiers except for one slave. In response, Capelle wrote to Cape Colony officials, requesting reinforcements to deal with the "hostile natives." This series of events angered Cape Town leaders, as the men of Fort Lydsaamheid were involving themselves in conflicts when they were supposed to be preparing to leave. In addition, colony officials lambasted the men for their "lazy" lifestyle, often spending the days fishing instead of surveying the region. In April 1730, Cape Colony leaders resolved to evacuate the remaining men from the fort and bring them to Cape Town. On 27 December 1730, the last 133 Dutchmen boarded the Snuffelaar, arriving in Cape Town in January 1731. Before leaving, they stripped the fort of every remaining item, and demolished the palisade so that no other European power could seize it. Within three years of abandonment, the fort was an overgrown ruin, with only a few walls remaining standing.