The history of navigation, or the history of seafaring, is the art of directing vessels upon the open sea through the establishment of its position and course by means of traditional practice, geometry, astronomy, or special instruments. Many peoples have excelled as seafarers, prominent among them the Austronesians (Islander Southeast Asians, Malagasy, Islander Melanesians, Micronesians, and Polynesians), the Harappans, the Phoenicians, the Iranians, the ancient Greeks, the Romans, the Arabs, the ancient Indians, the Norse, the Chinese, the Venetians, the Genoese, the Hanseatic Germans, the Portuguese, the Spanish, the English, the French, the Dutch, and the Danes.

Navigation in the Indo-Pacific began with the maritime migrations of the Austronesians from Taiwan who spread southwards into Island Southeast Asia and Island Melanesia during a period between 3000 and 1000 BC. Their first long-distance voyaging was the colonization of Micronesia from the Philippines at around 1500 BC. By about 900 BC their descendants had spread more than 6,000 kilometers across the Pacific, reaching Tonga and Samoa. In this region, a distinctive Polynesian culture developed. Within the next few centuries Polynesians reached Hawaii, New Zealand, Easter Island and possibly South America. Polynesian navigators used a range of tools and methods, including observation of birds, star navigation, and use of waves and swells to detect nearby land. Songs, mythological stories, and star charts were used to help people remember important navigational information. Meanwhile, Austronesians in Island Southeast Asia began the first true maritime trade networks by about 1000 BC, linking China, southern India, the Middle East, and coastal eastern Africa. Settlers from Borneo reached Madagascar by the early 1st millennium AD and colonized it by AD 500.

Sailors navigating in the Mediterranean made use of several techniques to determine their location, including staying in sight of land and understanding of the winds and their tendencies. Minoans of Crete are an example of an early Western civilization that used celestial navigation. Their palaces and mountaintop sanctuaries exhibit architectural features that align with the rising sun on the equinoxes, as well as the rising and setting of particular stars. The Minoans made sea voyages to the island of Thera and to Egypt. Both of these trips would have taken more than a day's sail for the Minoans and would have left them traveling by night across open water. Here the sailors would use the locations of particular stars, especially those of the constellation Ursa Major, to orient the ship in the correct direction.

Written records of navigation using stars, or celestial navigation, go back to Homer's Odyssey where Calypso tells Odysseus to keep the Bear (Ursa Major) on his left hand side and at the same time to observe the position of the Pleiades, the late-setting Boötes and the Orion as he sailed eastward from her island Ogygia traversing the Ocean. The Greek poet Aratus wrote in his Phainomena in the third century BC detailed positions of the constellations as written by Eudoxos. The positions described do not match the locations of the stars during Aratus' or Eudoxos' time for the Greek mainland, but some argue that they match the sky from Crete during the Bronze Age. This change in the position of the stars is due to the wobble of the Earth on its axis which affects primarily the pole stars. Around 1000 BC the constellation Draco would have been closer to the North Pole than Polaris. The pole stars were used to navigate because they did not disappear below the horizon and could be seen consistently throughout the night.

By the third century BC the Greeks had begun to use the Little Bear, Ursa Minor, to navigate. In the mid-1st century AD Lucan writes of Pompey who questions a sailor about the use of stars in navigation. The sailor replies with his description of the use of circumpolar stars to navigate by. To navigate along a degree of latitude a sailor would have needed to find a circumpolar star above that degree in the sky. For example, Apollonius would have used β Draconis to navigate as he traveled west from the mouth of the Alpheus River to Syracuse.

The voyage of the Greek navigator Pytheas of Massalia is a particularly notable example of a very long, early voyage. A competent astronomer and geographer, Pytheas ventured from Greece through the strait of Gibraltar to Western Europe and the British Isles. Pytheas is the first known person to describe the Midnight Sun, polar ice, Germanic tribes and possibly Stonehenge. Pytheas also introduced the idea of distant "Thule" to the geographic imagination and his account is the earliest to state that the Moon is the cause of the tides.

Nearchos's celebrated voyage from India to Susa after Alexander's expedition in India is preserved in Arrian's account, the Indica. Greek navigator Eudoxus of Cyzicus explored the Arabian Sea for Ptolemy VIII, king of the Hellenistic Ptolemaic dynasty in Egypt. According to Poseidonius, later reported in Strabo's Geography, the monsoon wind system of the Indian Ocean was first sailed by Eudoxus of Cyzicus in 118 or 116 BC.

Nautical charts and textual descriptions known as sailing directions have been in use in one form or another since the sixth century BC. Nautical charts using stereographic and orthographic projections date back to the second century BC.