Tibetans are well adapted to high altitude environments. Among the adaptive traits in Tibetans, the relatively low hemoglobin level is considered a blunted erythropoietic response to hypoxic challenge. Previously, EPAS1 and EGLN1, the major upstream regulators in the hypoxic pathway were reportedly involved in the hemoglobin regulation in Tibetans. In this study, we report a downstream gene (HMOX2) involved in heme catabolism, which harbors potentially adaptive variants in Tibetans. We first re-sequenced the entire genomic region (45.6 kb) of HMOX2 in Tibetans, which confirmed the previously suspected signal of positive selection on HMOX2 in Tibetans. Subsequent association analyses of hemoglobin levels in two independent Tibetan populations (a total of 1,250 individuals) showed a male-specific association between the HMOX2 variants and hemoglobin levels. Tibetan males with the derived C allele at rs4786504 displayed lower hemoglobin level as compared to the T allele carriers. Furthermore, our in vitro experiments indicated that the C allele of rs4786504 could increase the expression of HMOX2, presumably leading to a more efficient breakdown of heme that may help maintain a relatively low hemoglobin level at high altitude. Collectively, we propose that HMOX2 contributes to high altitude adaptation in Tibetans by functioning as a modifier in the regulation of hemoglobin metabolism.