Perchlorate has been widely detected in various water environments and could cause serious health problems. Methane has been proposed as a promising electron donor to remove perchlorate from contaminated water, yet it is unclear whether and how microbial methane oxidation couples with perchlorate reduction, in particular under anoxic conditions. Here, the feasibility and performance of perchlorate reduction driven by methane in the presence and absence of oxygen were investigated and compared in a lab-scale methane-based membrane biofilm reactor. Long-term operational performance suggested that perchlorate was reduced to chloride, with 4 mg Cl/L/d of perchlorate removal rate under anoxic conditions. Differently, perchlorate removal rate increased to 16 mg Cl/L/d, and volatile fatty acids (VFAs) were produced from methane partial oxidation when a limited oxygen (10 mg/L/d) was externally supplied. Regardless of oxygen conditions, microbial perchlorate reduction driven by methane might be mediated through synergistic interactions by a microbial consortium, but with different key microbial members under both oxygen regimes. Under anoxic conditions, aerobic methanotrophs (likely Methylocystaceae and Methylococcaceae) might micro-aerobically oxidize methane by utilizing internal oxygen from microbial perchlorate reduction, which might be mediated by Rhodocyclaceae. In contrast, under oxygen-limiting conditions, methanogens (e.g., Methanosarcina) and fermenters (e.g., Veillonellaceae) likely jointly converted methane into VFAs, then dissimilatory perchlorate-reducing bacteria (e.g., Rhodocyclaceae) utilized the produced VFAs to reduce perchlorate to chloride. Our findings provide evidence to link methane oxidation with perchlorate reduction under both oxygen regimes, which could be facilitated to design a process to remove perchlorate from groundwater.