Tides raised on a planet by its host star's gravity can reduce a planet's orbital semi-major axis and eccentricity. This effect is only relevant for planets orbiting very close to their host stars. The habitable zones of low-mass stars are also close-in and tides can alter the orbits of planets in these locations. We calculate the tidal evolution of hypothetical terrestrial planets around low-mass stars and show that tides can evolve planets past the inner edge of the habitable zone, sometimes in less than 1 billion years. This migration requires large eccentricities (>0.5) and low-mass stars (<0.35 M_Sun). Such migration may have important implications for the evolution of the atmosphere, internal heating and the Gaia hypothesis. Similarly, a planet detected interior to the habitable zone could have been habitable in the past. We consider the past habitability of the recently-discovered, ~5 M_Earth planet, Gliese 581 c. We find that it could have been habitable for reasonable choices of orbital and physical properties as recently as 2 Gyr ago. However, when we include constraints derived from the additional companions, we see that most parameter choices that predict past habitability require the two inner planets of the system to have crossed their mutual 3:1 mean motion resonance. As this crossing would likely have resulted in resonance capture, which is not observed, we conclude that Gl 581 c was probably never habitable.

31 pages, 10 figures, accepted to Astrobiology. A version with full resolution figures is available at http://www.lpl.arizona.edu/~rory/publications/brjg07.pdf