Despite numerous studies on bacterial motility, little is known about the regulation of this process by environmental factors in natural isolates. In this study we investigated the control of bacterial motility in response to environmental parameters in two strains isolated from the natural habitat of Lake Baikal. Morphological characterization, carbon source utilization, fermentation analysis, and sequence comparison of 16S rRNA genes showed that these strains belong to two distinct genera, i.e., Enterobacter and Pseudomonas; they were named strains 22 and Y1000, respectively. Both strains swarmed at 25°C and remained motile at low temperatures (4°C), especially the Pseudomonas strain, which further supports the psychrotrophic characteristics of this strain. In contrast, a strong inhibition of motility was observed at above 30°C and with a high NaCl concentration. The existence of flagellar regulatory proteins FlhDC and FleQ was demonstrated in Enterobacter strain 22 and Pseudomonas strain Y1000, respectively, and environmental conditions reduced the expression of the structural genes potentially located at the first level in the flagellar cascade in both organisms. Finally, as in Enterobacter strain 22, a strong reduction in the transcription of the master regulatory gene fleQ was observed in Pseudomonas strain Y1000 in the presence of novobiocin, a DNA gyrase inhibitor, suggesting a link between DNA supercoiling and motility control by environmental factors. Thus, striking similarities observed in the two organisms suggest that these processes have evolved toward a similar regulatory mechanism in polarly flagellated and laterally flagellated (peritrichous) bacteria.