Woolly mammoths had a set of adaptations that enabled them to thrive in the Arctic environment. Many mammoth-specific single nucleotide polymorphisms (SNPs) responsible for unique mammoth traits have been previously identified from ancient genomes. However, a multitude of other genetic variants likely contributed to woolly mammoth evolution. In this study, we sequenced two woolly mammoth genomes and combined these with previously sequenced mammoth and elephant genomes to conduct a survey of mammoth-specific deletions and indels. We find that deletions are highly enriched in non-coding regions, suggesting selection against structural variants that affect protein sequences. Nonetheless, at least 87 woolly mammoth genes contain deletions or indels that modify the coding sequence, including genes involved in skeletal morphology and hair growth. These results suggest that deletions and indels contributed to the unique phenotypic adaptations of the woolly mammoth, and were potentially critical to surviving in its natural environment.