The presence of hypoxic regions in solid tumors is an adverse prognostic factor for patient outcome. Here, we show that hypoxia induces the expression of Ephrin-A3 through a novel hypoxia-inducible factor (HIF)-mediated mechanism. In response to hypoxia, the coding EFNA3 mRNA levels remained relatively stable, but HIFs drove the expression of previously unknown long noncoding (lnc) RNAs from EFNA3 locus and these lncRNA caused Ephrin-A3 protein accumulation. Ephrins are cell surface proteins that regulate diverse biological processes by modulating cellular adhesion and repulsion. Mounting evidence implicates deregulated ephrin function in multiple aspects of tumor biology. We demonstrate that sustained expression of both Ephrin-A3 and novel EFNA3 lncRNAs increased the metastatic potential of human breast cancer cells, possibly by increasing the ability of tumor cells to extravasate from the blood vessels into surrounding tissue. In agreement, we found a strong correlation between high EFNA3 expression and shorter metastasis-free survival in breast cancer patients. Taken together, our results suggest that hypoxia could contribute to metastatic spread of breast cancer via HIF-mediated induction of EFNA3 lncRNAs and subsequent Ephrin-A3 protein accumulation.