Sulfate-reducing bacteria such as Desulfovibrio vulgaris Hildenborough are often found in environments with limiting growth nutrients. Using lactate as the electron donor and carbon source, and sulfate as the electron acceptor, wild type D. vulgaris shows motility on soft agar plates. We evaluated this phenotype with mutants resulting from insertional inactivation of genes potentially related to motility. Our study revealed that the cheA3 (DVU2072) kinase mutant was impaired in the ability to form motility halos. Insertions in two other cheA loci did not exhibit a loss in this phenotype. The cheA3 mutant was also non-motile in capillary assays. Complementation with a plasmid-borne copy of cheA3 restores wild type phenotypes. The cheA3 mutant displayed a flagellum as observed by electron microscopy, grew normally in liquid medium, and was motile in wet mounts. In the growth conditions used, the D. vulgaris ΔfliA mutant (DVU3229) for FliA, predicted to regulate flagella-related genes including cheA3, was defective both in flagellum formation and in forming the motility halos. In contrast, a deletion of the flp gene (DVU2116) encoding a pilin-related protein was similar to wild type. We conclude that wild type D. vulgaris forms motility halos on solid media that are mediated by flagella-related mechanisms via the CheA3 kinase. The conditions under which the CheA1 (DVU1594) and CheA2 (DVU1960) kinase function remain to be explored.