The conditions which led to the formation of the valley networks on Mars were apparently very different from present-day conditions. In this paper we investigate the relative importance of higher early surface temperatures versus higher deep regolith temperatures in producing a shallower depth to liquid water in the regolith on Mars. If enough CO2 is in the atmosphere, the surface temperature could be raised to near the freezing point around 3.8 b.y. ago despite a possibly weak early sun, at least in the equatorial regions. On the other hand, it has been argued that higher internal regolith temperatures, associated with a much higher heat flow around 3.8 b.y. ago than at present, could reduce the depth to liquid water sufficiently to account for the change in erosional style with time. In fact, it does not make sense on physical grounds to consider these two mechanisms separately. The effectiveness of both of these mechanisms is dependent on a high early heat flow. In general, we find that if early heat flow were around 100 mW m-2, then the total available CO2 in the atmosphere-plus-regolith system becomes critical. If total available CO2 were greater than about 4 bars, then the atmospheric greenhouse effect could play an important role in raising the liquid water level closer to the surface, but only in equatorial regions. On a global basis, condensation of large amounts of atmospheric CO2 may inhibit surface warming. If the total CO2 were 1 bar or less, the atmospheric greenhouse effect raises the surface warming. If the total CO2 were 1 bar or less, the atmospheric greenhouse effect raises the surface temperature by only a few degrees. Heat flows greater than 100 mW m-2 can still raise the liquid water level from over 1 km to less than 350 m, enabling substantially more efficient network formation very early in Martian history. ¿ American Geophysical Union 1993