Hypoxic conditions often persist within poorly vascularized tumors. At the cellular level constitutive activation of transcriptional regulators of the hypoxic response leads to the emergence of clones with aggressive phenotypes. The primary interface between the cell and the hypoxic environment is the plasma membrane. A detailed investigation of this organelle is expected to yield further targets for therapeutic perturbation of the response to hypoxia. In the present study, quantitative proteomic analysis of plasma membrane from hypoxia-adapted murine B16F10 melanoma was performed using differential 16O/18O stable isotopic labeling and multidimensional liquid chromatography-tandem mass spectrometry. The analysis resulted in the identification of 24,853 tryptic peptides, providing quantitative information for 2,433 proteins. For a subset of plasma membrane and secreted proteins, quantitative RT-PCR was used to gain further insight into the genomic regulatory events underlying the response to hypoxia. Consistent increases at the proteomic and transcriptomic levels were observed for aminopeptidase N (CD13), carbonic anhydrase IX, potassium-transporting ATPase, matrix metalloproteinase 9, and stromal cell derived factor I (SDF-1). Antibody-based analysis of a panel of human melanoma cell lines confirmed that CD13 and SDF-1 were consistently upregulated during hypoxia. This study provides the basis for the discovery of novel hypoxia-induced membrane proteins.