Under present climatic conditions streams and lakes on Mars will freeze. Freezing is slow and would have a negligible effect in impeding flow of the large floods that are believed to have eroded the outflow channels. Valley networks are more difficult to form under current climatic conditions since they appear to have formed by slow erosion by streams of modest discharges. Freezing of small Martian streams was modeled for a variety of climatic conditions on the supposition that the Martian atmosphere may have been considerably thicker in the past when the valley networks formed. The modeling involves examination of the energy balance at the upper and lower surfaces of ice on streams to determine the rate at which the ice thickens with time. The results indicate that freezing rates are not strongly dependent on atmospheric pressure. With no wind, increasing the pressure by a factor of 10 cuts the time taken to freeze solid only by about a factor of about 2. Under windy conditions dependence on atmospheric pressure is even weaker. The distance that water could travel in a stream before flow is arrested by freezing is also calculated. The distances depend on the initial temperature of the stream and when icings develop, but in general, if a stream deeper than 2 m can be initiated and sustained, the water within it can survive long enough to cut most of the valley networks observed. The main problem with forming the valley is initiating the flow. Groundwater seepage alone appears inadequate because of the difficulty of recharging the groundwater system. Melting of ice precipitated onto the surface following injection of water into the atmosphere by large impacts is a possible source of water, but the climatic conditions under which the ice could melt and the water be collected into streams that can survive long enough to cut the valley is uncertain.