There is consensus that the modern human lineage appeared in Africa before 100,000 years ago. But there is debate as to when cultural and cognitive characteristics typical of modern humans first appeared, and the role that these had in the expansion of modern humans out of Africa. Scientists rely on symbolically specific proxies, such as artistic expression, to document the origins of complex cognition. Advanced technologies with elaborate chains of production are also proxies, as these often demand high-fidelity transmission and thus language. Some argue that advanced technologies in Africa appear and disappear and thus do not indicate complex cognition exclusive to early modern humans in Africa. The origins of composite tools and advanced projectile weapons figure prominently in modern human evolution research, and the latter have been argued to have been in the exclusive possession of modern humans. Here we describe a previously unrecognized advanced stone tool technology from Pinnacle Point Site 5-6 on the south coast of South Africa, originating approximately 71,000 years ago. This technology is dominated by the production of small bladelets (microliths) primarily from heat-treated stone. There is agreement that microlithic technology was used to create composite tool components as part of advanced projectile weapons. Microliths were common worldwide by the mid-Holocene epoch, but have a patchy pattern of first appearance that is rarely earlier than 40,000 years ago, and were thought to appear briefly between 65,000 and 60,000 years ago in South Africa and then disappear. Our research extends this record to ∼71,000 years, shows that microlithic technology originated early in South Africa, evolved over a vast time span (∼11,000 years), and was typically coupled to complex heat treatment that persisted for nearly 100,000 years. Advanced technologies in Africa were early and enduring; a small sample of excavated sites in Africa is the best explanation for any perceived 'flickering' pattern.