Myoglobin is an oxygen storage molecule that is selectively expressed in cardiac and slow-twitch skeletal muscles that have a high oxygen demand. Numerous studies have implicated hypoxia in the regulation of myoglobin expression as an adaptive response to hypoxic stress. However, the details of this relationship remain undefined. In the present study, adult mice exposed to 10% oxygen for periods up to three weeks exhibited increased myoglobin expression only in the working heart, whereas myoglobin was either diminished or unchanged in skeletal muscle groups. In vitro and in vivo studies revealed that hypoxia in the presence or absence of exercise-induced stimuli, reprograms calcium signaling and modulates myoglobin gene expression. Hypoxia, alone significantly altered calcium influx in response to cell depolarization or depletion of endoplasmic reticulum calcium stores, which inhibited the expression of myoglobin. In contrast, our whole animal and transcriptional studies indicate that hypoxia in combination with exercise enhanced the release of calcium from the sarcoplasmic reticulum via the ryanodine receptors triggered by caffeine, which increased the translocation of NFAT (nuclear factor of activated T-cells) into the nucleus to transcriptionally activate myoglobin expression. The present study unveils a previously unrecognized mechanism where the hypoxia-mediated regulation of calcium transients from different intracellular pools modulates myoglobin gene expression. In addition, we observed that changes in myoglobin expression, in response to hypoxia, are not dependent on hypoxia inducible factor-1 or changes in skeletal muscle fiber type. These studies enhance our understanding of hypoxia-mediated gene regulation and will have broad applications for the treatment of myopathic diseases.