Methyl halides are used as agricultural fumigants and are precursor molecules that can be catalytically converted to chemicals and fuels. Plants and microorganisms naturally produce methyl halides, but these organisms produce very low yields or are not amenable to industrial production. A single methyl halide transferase (MHT) enzyme transfers the methyl group from the ubiquitous metabolite S-adenoyl methionine (SAM) to a halide ion. Using a synthetic metagenomic approach, we chemically synthesized all 89 putative MHT genes from plants, fungi, bacteria, and unidentified organisms present in the NCBI sequence database. The set was screened in Escherichia coli to identify the rates of CH3Cl, CH3Br, and CH3I production, with 56% of the library active on chloride, 85% on bromide, and 69% on iodide. Expression of the highest activity MHT and subsequent engineering in Saccharomyces cerevisiae results in productivity of 190 mg/L-h from glucose and sucrose. Using a symbiotic co-culture of the engineered yeast and the cellulolytic bacterium Actinotalea fermentans, we are able to achieve methyl halide production from unprocessed switchgrass (Panicum virgatum), corn stover, sugar cane bagasse, and poplar (Populus sp.). These results demonstrate the potential of producing methyl halides from non-food agricultural resources.