Theoretical arguments are presented in support of the idea that Mars possessed a dense CO2 atmosphere and a wet, warm climate early in its history. Calculations with a one-dimensional radiative-convective climate model indicate that CO2 pressures between 1 and 5 bars would have been required to keep the surface temperature above the freezing point of water early in the planet's history. The higher value corresponds to globally and orbitally averaged conditions and a 30% reduction in solar luminosity; the lower value corresponds to conditions at the equator during perihelion at times of high orbital eccentricity and the same reduced solar luminosity. The plausibility of such a CO2 greenhouse is tested by formulating a simple model of the CO2 geochemical cycle on early Mars. By appropriately scaling the rate of silicate weathering on present Earth, we estimate a weathering time constant of the order of several times 10(7) years for early Mars. Thus, a dense atmosphere could have persisted for a geologically significant time period (approximately 10(9) years) only if atmospheric CO2 was being continuously resupplied. The most likely mechanism by which this might have been accomplished is the thermal decomposition of carbonate rocks induced directly and indirectly (through burial) by intense, global-scale volcanism. For plausible values of the early heat flux, the recycling time constant is also of the order of several times 10(7) years. The amount of CO2 dissolved in standing bodies of water was probably small; thus, the total surficial CO2 inventory required to maintain these conditions was approximately 2 to 10 bars. The amount of CO2 in Mars' atmosphere would eventually have dwindled, and the climate cooled, as the planet's internal heat engine ran down. A test for this theory will be provided by spectroscopic searches for carbonates in Mars' crust.