Metastases formation is a major factor in disease progression and accounts for the majority of cancer deaths. The molecular mechanisms controlling invasion, dissemination to blood or lymphatic systems and spread of tumor cells to distant organs are still poorly understood. Recent observations indicate that the metastatic phenotype may already be present during the angiogenic switch of tumors. Intratumoral hypoxia correlates with poor prognosis and enhanced metastases formation. The Hypoxia Inducible Factors (HIFs) are key molecules in the hypoxic response and play critical roles during tumor cell expansion by regulating energy metabolism and the induction of angiogenesis. Increasing evidence implicates HIF function in metastatic cell characteristics, like epithelial to mesenchymal transition, cell detachment, invasion and tumor cell seeding. Here, we review the link between tumor cell hypoxia and the acquisition of metastatic behavior. We hypothesize that polyclonal tumor selection by hypoxia enhances metastatic capacity by transcriptional control of key regulators of metastasis. This polyclonal hypoxic gene profile potentially develops into a metastatic profile, driving metastasis formation. The hypoxic gene profile in primary tumors may therefore provide a prognostic indicator in clinical decision-making.