As a tumor grows, it requires increased amounts of oxygen. However, the tumor blood vessels that form to meet this demand are functionally impaired, leading to regions of hypoxia within the tumor. Such hypoxia is one of the hallmarks of malignancy and is thought to promote a number of tumorigenic properties. Here, we sought to determine how tumors without hypoxia would progress by engineering A549 human lung carcinoma cells to ectopically express myoglobin (Mb), a multifunctional heme protein that specializes in oxygen transport, storage, and buffering. Mb expression prevented the hypoxic response in vitro and delayed tumor engraftment and reduced tumor growth following xenotransplantation into mice. Experimental tumors expressing Mb displayed reduced or no hypoxia, minimal HIF-1α levels, and a homogeneously low vessel density. Mb-mediated tumor oxygenation promoted differentiation of cancer cells and suppressed both local and distal metastatic spreading. These effects were primarily due to reduced tumor hypoxia, because they were not observed using point-mutated forms of myoglobin unable to bind oxygen and they were abrogated by expression of a constitutively active form of HIF-1α. Although limited to xenograft models, these data provide experimental proof of the concept that hypoxia is not just a side effect of deregulated growth but a key factor on which the tumor relies in order to promote its own expansion.