Although freshwater (FW) is the ancestral habitat for larval mosquitoes, multiple species independently evolved the ability to survive in saltwater (SW). Here, we use quantitative trait locus (QTL) mapping to investigate the genetic architecture of osmoregulation in Anopheles mosquitoes, vectors of human malaria. We analyzed 1134 backcross progeny from a cross between the obligate FW species An. coluzzii, and its closely related euryhaline sibling species An. merus. Tests of 2387 markers with Bayesian interval mapping and machine learning (random forests) yielded six genomic regions associated with SW tolerance. Overlap in QTL regions from both approaches enhances confidence in QTL identification. Evidence exists for synergistic as well as disruptive epistasis among loci. Intriguingly, one QTL region containing ion transporters spans the 2Rop chromosomal inversion that distinguishes these species. Rather than a simple trait controlled by one or a few loci, our data are most consistent with a complex, polygenic mode of inheritance.