The diverse biota of New Guinea includes many nominally widespread species that actually comprise multiple deeply divergent lineages with more localised histories of evolution. Here we investigate the systematics of the very large geckos of the Cyrtodactylus novaeguineae complex using molecular and morphological data. These data reveal two widespread and divergent lineages that can be distinguished from each other, and from type material of Cyrtodactylus novaeguineae, by aspects of size, build, coloration and male scalation. On the basis of these differences we describe two new species. Both have wide distributions that overlap extensively in the foothill forests of the North Papuan Mountains, however one is seemingly restricted to hill and lower montane forests on the ranges themselves, while the other is more widespread throughout the surrounding lowlands. The taxon endemic to the North Papuan Mountains is related to an apparently lowland form currently known only from Waigeo and Batanta Island far to the west - hinting at a history on island arcs that accreted to form the North Papuan Mountains.