The southwest Pacific malaria vector Anopheles koliensis (Owen) is one of over 13 cryptic member species of the Anopheles punctulatus group and exists through the continual wet lowlands of New Guinea and requires rDNA-based PCR tools for species identification. Past field studies in northern Papua New Guinea (PNG) suggested that An. koliensis comprised three rDNA variants that exhibit differences in night biting profiles. In following up this study using nuclear and mitochondrial DNA sequences as well as 12 novel microsatellites, we confirm the presence of these three rDNA variants but only found evidence to support the existence of two putative species with microsatellites. We find this mosquito to have had a long history in New Guinea with overt genetic and geographic population structure. Landscape genetic analyses suggests that this broad-scale population structure of this mosquito is best explained when considering the landscape topology of New Guinea.