Several bacteria are able to degrade the major industrial solvent dichloromethane (DCM) by using the conserved dehalogenase DcmA, the only system for DCM degradation characterised at the sequence level so far. Using differential proteomics, we rapidly identified key determinants of DCM degradation for Hyphomicrobium sp. MC8b, an unsequenced facultative methylotrophic DCM-degrading strain. For this, we designed a pan-proteomics database comprising the annotated genome sequences of 13 distinct Hyphomicrobium strains. Compared to growth with methanol, growth with DCM induces drastic changes in the proteome of strain MC8b. Dichloromethane dehalogenase DcmA was detected by differential pan-proteomics, but only with poor sequence coverage, suggesting atypical characteristics of the DCM dehalogenation system in this strain. More peptides were assigned to DcmA by error-tolerant search, warranting subsequent sequencing of the genome of strain MC8b, which revealed a highly divergent set of dcm genes in this strain. This suggests that the dcm enzymatic system is less strongly conserved than previously believed, and that substantial molecular evolution of dcm genes has occurred beyond their horizontal transfer in the bacterial domain. Our study showed the power of pan-proteomics for quick characterization of new strains belonging to branches of the Tree of Life that are densely genome-sequenced.