Context.Thanks to remarkable progress, radial velocity surveys are now able to detect terrestrial planets at habitable distance from low-mass stars. Recently, two planets with minimum masses below 10 $M_{\oplus}$ have been reported in a triple system around the M-type star Gliese 581. These planets are found at orbital distances comparable to the location of the boundaries of the habitable zone of their star. Aims.In this study, we assess the habitability of planets Gl 581c and Gl 581d (assuming that their actual masses are close to their minimum masses) by estimating the locations of the habitable-zone boundaries of the star and discussing the uncertainties affecting their determination. An additional purpose of this paper is to provide simplified formulae for estimating the edges of the habitable zone. These may be used to evaluate the astrobiological potential of terrestrial exoplanets that will hopefully be discovered in the near future. Methods.Using results from radiative-convective atmospheric models and constraints from the evolution of Venus and Mars, we derive theoretical and empirical habitable distances for stars of F, G, K, and M spectral types. Results.Planets Gl 581c and Gl 581d are near to, but outside, what can be considered as the conservative habitable zone. Planet “c” receives 30% more energy from its star than Venus from the Sun, with an increased radiative forcing caused by the spectral energy distribution of Gl 581. This planet is thus unlikely to host liquid water, although its habitability cannot be positively ruled out by theoretical models due to uncertainties affecting cloud properties and cloud cover. Highly reflective clouds covering at least 75% of the day side of the planet could indeed prevent the water reservoir from being entirely vaporized. Irradiation conditions of planet “d” are comparable to those of early Mars, which is known to have hosted surface liquid water. Thanks to the greenhouse effect of CO2-ice clouds, also invoked to explain the early Martian climate, planet “d” might be a better candidate for the first exoplanet known to be potentially habitable. A mixture of several greenhouse gases could also maintain habitable conditions on this planet, although the geochemical processes that could stabilize such a super-greenhouse atmosphere are still unknown.