Waste metalworking fluids (MWFs) are highly biocidal resulting in real difficulties in the, otherwise favoured, bioremediation of these high chemical oxygen deman (COD) wastes anaerobically in bioreactors. We have shown, as a proof of concept, that it is possible to establish an anaerobic starter culture using strains isolated from spent MWFs which are capable of reducing COD or, most significantly, methanogenesis in this biocidal waste stream. Bacterial strains (n = 99) and archaeal methanogens (n = 28) were isolated from spent MWFs. The most common bacterial strains were Clostridium species (n = 45). All methanogens were identified as Methanosarcina mazei. Using a random partitions design (RPD) mesocosm experiment, we found that bacterial diversity and species–species interactions had significant effects on COD reduction but that bacterial composition did not. The RPD study showed similar effects on methanogenesis, except that composition was also significant. We identified bacterial species with positive and negative effects on methane production. A consortium of 16 bacterial species and three methanogens was used to initiate a fluidized bed bioreactor (FBR), in batch mode. COD reduction and methane production were variable, and the reactor was oscillated between continuous and batch feeds. In both microcosm and FBR experiments, periodic inconsistencies in bacterial reduction in fermentative products to formic and acetic acids were identified as a key issue.