Genome sequences are known for two archaic hominins—Neanderthals and Denisovans—which interbred with anatomically modern humans as they dispersed out of Africa. We identified high-confidence archaic haplotypes in 161 new genomes spanning 14 island groups in Island Southeast Asia and New Guinea and found large stretches of DNA that are inconsistent with a single introgressing Denisovan origin. Instead, modern Papuans carry hundreds of gene variants from two deeply divergent Denisovan lineages that separated over 350 thousand years ago. Spatial and temporal structure among these lineages suggest that introgression from one of these Denisovan groups predominantly took place east of the Wallace line and continued until near the end of the Pleistocene. A third Denisovan lineage occurs in modern East Asians. This regional mosaic suggests considerable complexity in archaic contact, with modern humans interbreeding with multiple Denisovan groups that were geographically isolated from each other over deep evolutionary time.