The emergence of agriculture was one of the most notable behavioral transformations in human history, driving innovations in technologies and settlement globally, referred to as the Neolithic. Wetland agriculture originated in the New Guinea highlands during the mid-Holocene (8000 to 4000 years ago), yet it is unclear if there was associated behavioral change. Here, we report the earliest figurative stone carving and formally manufactured pestles in Oceania, dating to 5050 to 4200 years ago. These discoveries, at the highland site of Waim, occur with the earliest planilateral axe-adzes in New Guinea, the first evidence for fibercraft, and interisland obsidian transfer. The combination of symbolic social systems, complex technologies, and highland agricultural intensification supports an independent emergence of a Neolithic ~1000 years before the arrival of Neolithic migrants (Lapita) from Southeast Asia.