Methane (CH4) on Mars has high scientific significance, especially its generation and destruction mechanisms. With an estimated photochemical lifetime of ~300 years, observations of sporadic methane plumes suggest the need for novel destruction mechanisms. Here, we report an experimental approach to study the CH4 destruction by heterogeneous electrochemistry (HEC) induced by Martian dust activities. A set of mid-strength electrostatic discharge (ESD) experiments was conducted in the mixtures of CO2+CH4 under the conditions relevant to the Martian near surface atmosphere. We characterized (1) the free radicals from the breakdown of CH4 and CO2; (2) the gaseous and solid products of CH4 breakdown; and (3) the half-life of CH4 in such ESD process. Our experimental investigation revealed a new mechanism with a CH4 destruction rate much faster than that of photochemistry. It suggests that Martian dust activities could be the major cause of shortening the lifetime of methane in the Martian atmosphere.