The increase in red blood cell mass (polycythemia) due to the reduced oxygen availability (hypoxia) of residence at high altitude or other conditions is generally thought to be beneficial in terms of increasing tissue oxygen supply. However, the extreme polycythemia and accompanying increased mortality due to heart failure in chronic mountain sickness most likely reduces fitness. Tibetan highlanders have adapted to high altitude, possibly in part via the selection of genetic variants associated with reduced polycythemic response to hypoxia. In contrast, high-altitude-adapted Quechua- and Aymara-speaking inhabitants of the Andean Altiplano are not protected from high-altitude polycythemia in the same way, yet they exhibit other adaptive features for which the genetic underpinnings remain obscure. Here, we used whole-genome sequencing to scan high-altitude Andeans for signals of selection. The genes showing the strongest evidence of selection-including BRINP3, NOS2, and TBX5-are associated with cardiovascular development and function but are not in the response-to-hypoxia pathway. Using association mapping, we demonstrated that the haplotypes under selection are associated with phenotypic variations related to cardiovascular health. We hypothesize that selection in response to hypoxia in Andeans could have vascular effects and could serve to mitigate the deleterious effects of polycythemia rather than reduce polycythemia itself.