Mammalian gene expression patterns change profoundly in response to low oxygen levels. These changes in gene expression programs are strongly influenced by post-transcriptional mechanisms mediated by mRNA-binding factors: RNA-binding proteins (RBPs) and microRNAs (miRNAs). Here, we review the RBPs and miRNAs that modulate mRNA turnover and translation in response to hypoxic challenge. RBPs such as HuR (human antigen R), PTB (polypyrimidine tract-binding protein), heterogeneous nuclear ribonucleoproteins (hnRNPs), tristetraprolin, nucleolin, iron-response element binding proteins (IRPs), and cytoplasmic polyadenylation-element-binding proteins (CPEBs), selectively bind to numerous hypoxia-regulated transcripts and play a major role in establishing hypoxic gene expression patterns. MiRNAs including miR-210, miR-373, and miR-21 associate with hypoxia-regulated transcripts and further modulate the levels of the encoded proteins to implement the hypoxic gene expression profile. We discuss the potent regulation of hypoxic gene expression by RBPs and miRNAs and their integrated actions in the cellular hypoxic response.