Allele sharing between modern and archaic hominin genomes has been variously interpreted to have originated from ancestral genetic structure or through non-African introgression from archaic hominins. However, evolution of variable human deletions that are shared with archaic hominin genomes have yet to be studied. We identified 427 variable human deletions that are shared with archaic hominin genomes, ~87% of which originated before the Human-Neandertal divergence (ancient) and only ~9% of which have been introgressed from Neandertals (introgressed). Recurrence, incomplete lineage sorting between human and chimp lineages, and hominid-specific insertions constitute the remaining ~4% of allele sharing between humans and archaic hominins. We observed that ancient deletions correspond to more than 13% of all common (>5% allele frequency) deletion variation among modern humans. 17 exonic deletions were shared with archaic hominin genomes, affecting genes involved in metabolism of external and internal compounds, growth and sperm formation, as well as susceptibility to psoriasis and Crohn’s disease. We found that these exonic deletion variants have likely evolved through balancing and population specific positive selection. Our findings reveal that human genomic structural variants that are shared with archaic hominin genomes are common in human populations and can influence biomedically and evolutionarily important phenotypes.