New Guinea is a topographically and biogeographically complex region that supports unique endemic fauna. Studies describing the population connectivity of species through this region are scarce. We present a population and landscape genetic study on the endemic malaria-transmitting mosquito, Anopheles koliensis (Owen). Using mitochondrial and nuclear sequence data, as well as microsatellites, we show the evidence of geographically discrete population structure within Papua New Guinea (PNG). We also confirm the existence of three rDNA ITS2 genotypes within this mosquito and assess reproductive isolation between individuals carrying different genotypes. Microsatellites reveal the clearest population structure and show four clear population units. Microsatellite markers also reveal probable reproductive isolation between sympatric populations in northern PNG with different ITS2 genotypes, suggesting that these populations may represent distinct cryptic species. Excluding individuals belonging to the newly identified putative cryptic species (ITS2 genotype 3), we modeled the genetic differences between A. koliensis populations through PNG as a function of terrain and find that dispersal is most likely along routes with low topographic relief. Overall, these results show that A. koliensis is made up of geographically and genetically discrete populations in Papua New Guinea with landscape topography being important in restricting dispersal.