Recent developments in shotgun proteomics have enabled high-throughput studies of a variety of microorganisms at a proteome level and provide experimental validation for predicted open reading frames in the corresponding genome. More importantly, advances in mass spectrometric data analysis now allow mining of large proteomics data sets for the presence of post-translational modifications (PTMs). Although PTMs are a critical aspect of cellular activity, such information eludes cell-wide studies conducted at the transcript level. Here, we analyze several mass spectrometric data sets acquired using two-dimensional liquid chromatography tandem mass spectrometry, 2D-LC/MS/MS, for the sulfate reducing bacterium, Desulfovibrio vulgaris Hildenborough. Our searches of the raw spectra led us to discover several post-translationally modified peptides in D. vulgaris. Of these, several peptides containing a lysine with a +42 Da modification were found reproducibly across all data sets. Both acetylation and trimethylation have the same nominal +42 Da mass, and are therefore candidates for this modification. Several spectra were identified having markers for trimethylation, while one is consistent with an acetylation. Surprisingly, these modified peptides predominantly mapped to proteins involved in sulfate respiration. Other highly expressed proteins in D. vulgaris, such as enzymes involved in electron transport and other central metabolic processes, did not contain this modification. Decoy database searches were used to control for random spectrum/sequence matches. Additional validation for these modifications was provided by alternate workflows, for example, two-dimensional gel electrophoresis followed by mass spectrometry analysis of the dissimilatory sulfite reductase gamma-subunit (DsrC) protein. MS data for DsrC in this alternate workflow also contained the +42 Da modification at the same loci. Furthermore, the DsrC homologue in another sulfate reducing bacterium, Desulfovibrio desulfuricans G20, also showed similar +42 Da modifications in the same pathway. Here, we discuss our methods and implications of potential trimethylation in the D. vulgaris sulfate reduction pathway.