The presence of valley networks and indications of high erosion rates in ancient terrains on Mars suggest that Mars was warm and wet during heavy bombardment. Various processes that could occur on early Mars were integrated into a self-consistent model to determine what circumstances might lead to warm temperatures during and at the end of heavy bombardment. Included were weathering and burial of CO2 as carbonates, impact erosion, sputtering, and recycling of CO2 back into the atmosphere by burial and heating. The models suggest that despite losses from the atmosphere by weathering and impact erosion, Mars could retain a 0.5 to 1 bar atmosphere at the end of heavy bombardment partly because weathering temporarily sequesters CO2 in the ground and protects it from impact erosion while the impact rate is declining and impact erosion is becoming less effective. Because of the low output of the early Sun, surface temperatures can be above freezing only for a very efficient greenhouse, such as that suggested by Forget and Pierrehumbert [1997]. With weak greenhouse models, temperatures are below freezing throughout heavy bombardment, and such a large amount of CO2 is left in the atmosphere at the end of heavy bombardment that it is difficult to eliminate subsequently to arrive at the present surface inventory. With strong greenhouse models, temperatures are well above freezing during heavy bombardment and drop to close to freezing at the end of heavy bombardment, at which time the atmosphere contains 0.5 to 1 bar of CO2. This can be largely eliminated subsequently by sputtering and low-temperature weathering. Such a model is consistent with the change in erosion rate and the declining rate of valley formation at the end of heavy bombardment. Conditions that favor warm temperatures at the end of heavy bombardment are an efficient greenhouse, low weathering rates, low impact erosion rates, and a smaller fraction of heat lost by conduction as opposed to transport of lava to the surface.