Genome sequences are known for two archaic hominins – Neanderthals and Denisovans – which interbred with anatomically modern humans as they dispersed out of Africa. By excavating archaic haplotypes from 161 new genomes spanning 14 island groups in Island Southeast Asia and Papua, we find large stretches of DNA that are inconsistent with a single introgressing Denisovan origin. Instead, modern Papuans carry hundreds of gene variants from at least two deeply divergent Denisovan lineages, separated by over 350 thousand years. Geographical structure in these lineages implies introgression from Denisovans that must have lived east of the Wallace line and suggests considerable complexity in archaic contact among Papuan groups. A third Denisovan lineage occurs in modern Siberians, Native Americans and East Asians. This regional mosaic suggests that modern humans interbred with multiple Denisovan populations, which were geographically isolated from each other over deep evolutionary time.