The presence of methane has been recently detected in the martian atmosphere, suggesting a contemporary source such as volcanism or microbial activity. Here we show that methane may be released by the destabilization of methane clathrate hydrates, triggered by the interglacial climate change starting 0.4 Ma. Clathrate hydrates are nonstoichiometric crystalline compounds in which a water ice lattice forms cages that contain apolar gas molecules, such as methane [CH4·nH2O] and carbon dioxide [CO2·nH2O]. The loss of shallow ground ice eliminates confining pressure, initiating the destabilization of clathrate hydrates and the release of methane to the atmosphere. This alternative process does not restrict the methane's age to 430 yr (maximum residence time of methane gas in martian atmosphere), because clathrate hydrates can preserve (encage) methane of ancient origin for long time periods.