Humans have inhabited the Andean Altiplano for over 11,000 years, where the partial pressure of oxygen is 35% lower than at sea level. Peruvian Quechua who thrive in this environment display a suite of adaptive phenotypes, such as elevated hemoglobin concentration ([Hb]). The genetic architecture contributing to this adaptive phenotype is currently unknown. To identify genomic regions associated with elevated [Hb] among Peruvian Quechua, we identified single nucleotide polymorphisms (SNPs) that display strong signatures of positive selection using four statistics: LSBL, iHS, XP-EHH, and XP-nSL. We then performed a genome-wide association study (GWAS) for elevated [Hb], restricting our analysis to SNPs showing evidence of past natural selection. As GWAS nominated SNPs often have small effect sizes and represent a small portion of all associated SNPs, we aggregated SNP effects across the genome by creating a phenotype prediction model using LASSO regression. From this investigation, we created a comprehensive list of putative regions of selection and found several genomic loci that are weakly associated with [Hb]. By investigating elevated hemoglobin concentration from a genomic perspective, this study contributes novel insights into the genetic basis of adaptive evolution among Peruvian Quechua, as well as the role of positive selection in shaping trait variation.