The presence of valleys on ancient terrains of Mars suggest that liquid water flowed on the martian surface 3.8 billion years ago or before. The above-freezing temperatures required to explain valley formation could have been transient, in response to frequent large meteorite impacts on early Mars, or they could have been caused by long-lived greenhouse warming. Climate models that consider only the greenhouse gases carbon dioxide and water vapor have been unable to recreate warm surface conditions, given the lower solar luminosity at that time. Here we use a one-dimensional climate model to demonstrate that an atmosphere containing 1.3-4 bar of CO2 and water vapor, along with 5 to 20 percent H2, could have raised the mean surface temperature of early Mars above the freezing point of water. Vigorous volcanic outgassing from a highly reduced early martian mantle is expected to provide sufficient atmospheric H2 and CO2, the latter from the photochemical oxidation of outgassed CH4 and CO, to form a CO2-H2 greenhouse. Such a dense early martian atmosphere is consistent with independent estimates of surface pressure based on cratering data.