Degassing of planetary interiors through surface volcanism plays an important role in the evolution of planetary bodies and atmospheres. On Earth, carbon dioxide and water are the primary volatile species in magmas. However, little is known about the speciation and degassing of carbon in magmas formed on other planets (i.e., Moon, Mars, Mercury), where the mantle oxidation state [oxygen fugacity (fO2)] is different from that of the Earth. Using experiments on a lunar basalt composition, we confirm that carbon dissolves as carbonate at an fO2 higher than -0.55 relative to the iron wustite oxygen buffer (IW-0.55), whereas at a lower fO2, we discover that carbon is present mainly as iron pentacarbonyl and in smaller amounts as methane in the melt. The transition of carbon speciation in mantle-derived melts at fO2 less than IW-0.55 is associated with a decrease in carbon solubility by a factor of 2. Thus, the fO2 controls carbon speciation and solubility in mantle-derived melts even more than previous data indicate, and the degassing of reduced carbon from Fe-rich basalts on planetary bodies would produce methane-bearing, CO-rich early atmospheres with a strong greenhouse potential.