Although genetic studies have contributed greatly to our understanding of the colonization of Near and Remote Oceania, important gaps still exist. One such gap is the Solomon Islands, which extend between Bougainville and Vanuatu, thereby bridging Near and Remote Oceania, and include both Austronesian-speaking and Papuan-speaking groups. Here, we describe patterns of mitochondrial DNA (mtDNA) and nonrecombining Y chromosome (NRY) variation in over 700 individuals from 18 populations in the Solomons, including 11 Austronesian-speaking groups, 3 Papuan-speaking groups, and 4 Polynesian Outliers (descended via back migration from Polynesia). We find evidence for ancient (pre-Lapita) colonization of the Solomons in old NRY paragroups as well as from M2-M353, which probably arose in the Solomons ∼9,200 years ago and is the most frequent NRY haplogroup there. There are no consistent genetic differences between Austronesian-speaking and Papuan-speaking groups, suggesting extensive genetic contact between them. Santa Cruz, which is located in Remote Oceania, shows unusually low frequencies of mtDNA and NRY haplogroups of recent Asian ancestry. This is in apparent contradiction with expectations based on archaeological and linguistic evidence for an early (∼3,200 years ago), direct colonization of Santa Cruz by Lapita people from the Bismarck Archipelago, via a migration that "leapfrogged" over the rest of the Solomons. Polynesian Outliers show dramatic island-specific founder events involving various NRY haplogroups. We also find that NRY, but not mtDNA, genetic distance is correlated with the geographic distance between Solomons groups and that historically attested spheres of cultural interaction are associated with the recent genetic structure of Solomons groups, as revealed by mtDNA HV1 sequence and Y-STR haplotype diversity. Our results fill an important lacuna in human genetic studies of Oceania and aid in understanding the colonization and genetic history of this region.