The Mars Odyssey space probe has discovered evidence of caves on Mars. They're way up high, on the upper slopes of Arsia Mons, which is a sister volcano to the largest volcano in the solar system, Olympus Mons. While it's quite unlikely these particular caverns could host life, their existence implies there may be caves at much lower altitudes which could provide shelter for current or former life.