Radial velocity surveys are now able to detect terrestrial planets at habitable distance from M-type stars. Recently, two planets with minimum masses below 10 Earth masses were reported in a triple system around the M-type star Gliese 581. Using results from atmospheric models and constraints from the evolution of Venus and Mars, we assess the habitability of planets Gl 581c and Gl 581d and we discuss the uncertainties affecting the habitable zone (HZ) boundaries determination. We provide simplified formulae to estimate the HZ limits that may be used to evaluate the astrobiological potential of terrestrial exoplanets that will hopefully be discovered in the near future. Planets Gl 581c and 'd' are near, but outside, what can be considered as the conservative HZ. 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. Its habitability cannot however be positively ruled out by theoretical models due to uncertainties affecting cloud properties. Irradiation conditions of planet 'd' are comparable with those of early Mars. Thanks to the warming effect of CO2-ice clouds planet 'd' might be a better candidate for the first exoplanet known to be potentially habitable. A mixture of various greenhouse gases could also maintain habitable conditions on this planet.Read less <