The origin of the martian methane is still poorly understood. A plausible explanation is that methane could have been produced either by hydrothermal alteration of basaltic crust or by serpentinization of ultramafic rocks producing hydrogen and reducing crustal carbon into methane. Once formed, methane storage on Mars is commonly associated with the presence of hidden clathrate reservoirs. Here, we alternatively suggest that chabazite and clinoptilolite, which belong to the family of zeolites, may form a plausible storage reservoir of methane in the martian subsurface. Because of the existence of many volcanic terrains, zeolites are expected to be widespread on Mars and their Global Equivalent Layer may range up to more than $\sim$1 km, according to the most optimistic estimates. If the martian methane present in chabazite and clinoptilolite is directly sourced from an abiotic source in the subsurface, the destabilization of a localized layer of a few millimeters per year may be sufficient to explain the current observations. The sporadic release of methane from these zeolites requires that they also remained isolated from the atmosphere during its evolution. The methane release over the ages could be due to several mechanisms such as impacts, seismic activity or erosion. If the methane outgassing from excavated chabazite and/or clinoptilolite prevails on Mars, then the presence of these zeolites around Gale Crater could explain the variation of methane level observed by Mars Science Laboratory.