Protein-protein interactions offer an insight into cellular processes beyond what may be obtained by the quantitative functional genomics tools of proteomics and transcriptomics. The aforementioned tools have been extensively applied to study Escherichia coli and other aerobes and more recently to study the stress response behavior of Desulfovibrio vulgaris Hildenborough, a model obligate anaerobe and sulfate reducer and the subject of this study. Here we carried out affinity purification followed by mass spectrometry to reconstruct an interaction network among 12 chromosomally encoded bait and 90 prey proteins based on 134 bait-prey interactions identified to be of high confidence. Protein-protein interaction data are often plagued by the lack of adequate controls and replication analyses necessary to assess confidence in the results, including identification of potential false positives. We addressed these issues through the use of biological replication, exponentially modified protein abundance indices, results from an experimental negative control, and a statistical test to assign confidence to each putative interacting pair applicable to small interaction data studies. We discuss the biological significance of metabolic features of D. vulgaris revealed by these protein-protein interaction data and the observed protein modifications. These include the distinct role of the putative carbon monoxide-induced hydrogenase, unique electron transfer routes associated with different oxidoreductases, and the possible role of methylation in regulating sulfate reduction.