Selenate (SeO4(2-)) bioreduction is possible with oxidation of a range of organic or inorganic electron donors, but it never has been reported with methane gas (CH4) as the electron donor. In this study, we achieved complete SeO4(2-) bioreduction in a membrane biofilm reactor (MBfR) using CH4 as the sole added electron donor. The introduction of nitrate (NO3(-)) slightly inhibited SeO4(2-) reduction, but the two oxyanions were simultaneously reduced, even when the supply rate of CH4 was limited. The main SeO4(2-)-reduction product was nanospherical Se(0), which was identified by scanning electron microscopy coupled to energy dispersive X-ray analysis (SEM-EDS). Community analysis provided evidence for two mechanisms for SeO4(2-) bioreduction in the CH4-based MBfR: a single methanotrophic genus, such as Methylomonas, performed CH4 oxidation directly coupled to SeO4(2-) reduction, and a methanotroph oxidized CH4 to form organic metabolites that were electron donors for a synergistic SeO4(2-)-reducing bacterium.