Vanadate contaminant in groundwater receives increasing attentions, but little is known on its biogeochemical transformation with gaseous electron donors. This study investigated bio-reduction of vanadate coupled with anaerobic methane oxidation and its relationship with nitrate reduction. Results showed 95.8 ± 3.1% of 1 mM vanadate was removed within 7 days using methane as the sole electron donor. Tetravalent vanadium compounds were the main reduction products, which precipitated naturally in groundwater environment. The introduction of nitrate inhibited vanadate reduction, though both were reduced in parallel. Accumulations of volatile fatty acids (VFAs) were observed from methane oxidation. Preliminary microbial community structure and metabolite analyses indicated that vanadate was likely reduced via Methylomonas coupled with methane oxidation or through synergistic relationships between methane oxidizing bacteria and heterotrophic vanadate reducers with VFAs served as the intermediates.