Regions with complex geological histories present a major challenge for scientists studying the processes that have shaped their biotas. The history of the vast and biologically rich tropical island of New Guinea is particularly complex and poorly resolved. Competing geological models propose New Guinea emerged as a substantial landmass either during the Mid-Miocene or as recently as the Pliocene. Likewise, the estimated timing for the uplift of the high Central Cordillera, spanning the length of the island, differs across models. Here we investigate how early islands and mountain uplift have shaped the diversification and biogeography of Cyrtodactylus geckos. Our data strongly support initial colonisation and divergence within proto-Papuan islands in the Early- to Mid-Miocene, with divergent lineages and endemic diversity concentrated on oceanic island arcs in northern New Guinea and the formerly isolated East-Papuan Composite Terrane. At least four lineages are inferred to have independently colonised hill- and lower-montane forests, indicating that mountain uplift has also played a critical role in accumulating diversity, even in this predominantly lowland lineage. Our findings suggest that substantial land in northern New Guinea and lower-montane habitats date back well into the Miocene and that insular diversification and mountain colonisation have synergistically generated diversity in the geologically complex Papuan region.