Prehistoric Indonesia is a prehistoric period in the Indonesian archipelago that spanned from the Pleistocene period to about the 4th century CE when the Kutai people produced the earliest known stone inscriptions in Indonesia. Unlike the clear distinction between prehistoric and historical periods in Europe and the Middle East, the division is muddled in Indonesia. This is mostly because Indonesia's geographical conditions as a vast archipelago caused some parts — especially the interiors of distant islands — to be virtually isolated from the rest of the world. West Java and coastal Eastern Borneo, for example, began their historical periods in the early 4th century, but megalithic culture still flourished and script was unknown in the rest of Indonesia, including in Nias and Toraja. The Papuans on the Indonesian part of New Guinea island lived virtually in the Stone Age until their first contacts with modern world in the early 20th century. Even today living megalithic traditions still can be found on the island of Sumba and Nias.

Geologically, the area of modern Indonesia appeared from under the Southeast Asian seas as the result of the Indian and Australian plates colliding and slipping under the Sunda Plate, sometime in the early Cenozoic era around 63 million years ago. This tectonic collision created the Sunda volcanic Arc that has produced the chains of islands of Sumatra, Java and the Lesser Sunda Islands. The active volcanic arc creating supervolcano that today become Lake Toba in Sumatra. The massive eruption of the Toba supervolcano that occurred some time between 69,000 and 77,000 years ago (72,000 BCE) instigated the Toba catastrophe theory, a global volcanic winter that caused a bottleneck in human evolution. Other notable volcanoes in Sunda Arc are Mount Tambora (erupted in 1815) and Krakatau (erupted in 1883). The region is known for its instability due to volcano formations and other volcanic and tectonic activities as well as climate changes; resulted in lowlands drowned occasionally under shallow seas, the formation of islands, the connection and disconnection of islands through narrow land-bridges, etc.

The Indonesian archipelago nearly reached its present form in the Pleistocene period. For some periods, the Sundaland was still linked with Asian mainland, creating the landmass extension of Southeast Asia that enabled the migrations of some Asian animals and hominid species. Geologically the New Guinea island and the shallow seas of Arafura is the northern part of Australia tectonic plate and once connected as a land bridge identified as Sahulland. During the end of the last ice age (around 20,000–10,000 years ago), earth experienced global climate change; a global warming with the rising of average temperature caused the melting of polar ice caps and contributed to the rising of sea surface. Sundaland was submerged under shallow sea, creating Malacca Strait, South China Sea, Karimata Strait and Java Sea. During that period, Malay Peninsula, Sumatra, Java, Borneo and the islands around them were formed. On the east, New Guinea and Aru Islands were separated from the Australia mainland. The rise of sea surface created isolated areas that separated plants, animals and hominid species, causing further evolution and specification.

In 2007 analysis of cut marks on two bovid bones found in Sangiran, showed them to have been made 1.5 to 1.6 million years ago by clamshell tools, and is the oldest evidence for the presence of early man in Indonesia. Fossilised remains of Homo erectus, popularly known as the "Java Man" were first discovered by the Dutch anatomist Eugène Dubois at Trinil in 1891, and are at least 700,000 years old, at that time the oldest human ancestor ever found. Further Homo erectus fossils of a similar age were found at Sangiran in the 1930s by the anthropologist Gustav Heinrich Ralph von Koenigswald, who in the same time period also uncovered fossils at Ngandong alongside more advanced tools, re-dated in 2011 to between 550,000 and 143,000 years old. In 1977 another Homo erectus skull was discovered at Sambungmacan.

In 2003, on the island of Flores, fossils of a new small hominid dated between 74,000 and 13,000 years old and named "Flores Man" (Homo floresiensis) were discovered much to the surprise of the scientific community. This 3-foot-tall hominid is thought to be a species descended from Homo Erectus and reduced in size over thousands of years by a well known process called island dwarfism. Homo floresiensis was first dated to relatively recent time periods - as recent as 14,000 years ago, however re-examination of the sediments has revised these dates and these hominins have been shown to have been present in Indonesia since at least 700,000 years ago, until about 60–50,000 years ago. In 2010 stone tools were discovered on Flores dating from 1 million years ago.^{[failed verification]}

The archipelago was formed during the thaw after the latest ice age. Early humans travelled by sea and spread from mainland Asia eastward to New Guinea and Australia. Homo sapiens reached the region by around 45,000 years ago. In 2011 evidence was uncovered in neighbouring East Timor, showing that 42,000 years ago these early settlers had high-level maritime skills, and by implication the technology needed to make ocean crossings to reach Australia and other islands, as they were catching and consuming large numbers of big deep-sea fish such as tuna.

Early Homo sapiens reached the archipelago between 60,000 and 45,000 years ago. Many but not all Southeast Asian Homo sapiens fossils prior to about 8,000 BCE have been identified as being distinct from Austronesians. The remnants of the pre-Austronesian groups of Southeast Asia survive in isolated pockets in Malaysia (Semang) and the Philippines (Aeta). The descendants of the pre-Austronesian inhabitants of the Indonesian Archipelago are still the majority in the eastern portion of the region, in islands such as New Guinea, the Maluku and East Nusa Tenggara. Genetic studies show that in Western Papua there was significant genetic admixture between Negritos, Australo-Melanesians and Austronesians.

Approximately 40,000 years ago, early humans produced prehistoric rock art motifs in volcanic caves on the island of Sulawesi. This means that humans at both extremes of the Pleistocene Eurasian world, Europe and Indonesia, were producing rock art during the same time period. The most notable rock art sites in Indonesia are the Maros-Pangkep rock art sites at the caves in South Sulawesi province. There are two distinct styles of art within these caves, both dated to the Pleistocene period. The first consists of human hand stencils, made by spraying wet pigment spit from the mouth, around human hands that were pressed against the cave wall surfaces. The second is a less common style of cave art, characterized by images drawn of larger, naturalistic profile paintings of wild land mammals that were endemic to the island during the Pleistocene period, such as miniature buffalos and warty pigs.