Life at high altitude is associated with many physiological challenges, including exposure to conspicuous stressors such as hypoxia and extreme cold. Consequently, most animals living at high altitude have been under strong selection to develop adaptations to these challenges. Unveiling adaptations in other high-altitude-living animals, including nonhuman primates, could therefore help illuminate the mechanisms underlying adaptive evolution of myriad traits. Here, we investigated the genetic adaptations to high altitude in a novel nonhuman primate model, the gelada monkey. To do so we generated a de novo genome assembly and regulatory map of the gelada. We then investigated which gene families have undergone significant expansion in geladas compared to their close phylogenetic relatives, macaques, humans, and baboons. Next, we deeply sequenced DNA samples from 40 high altitude geladas and 20 low altitude hamadryas baboons. These data allowed us identify candidate loci that show signatures of positive selection in high-altitude geladas relative to their close phylogenetic relatives.