Four strains of filamentous bacteria were isolated from slimes collected in different paper mill factories. Morphological and physiological characterization of the isolates indicated an affiliation with the genus Sphaerotilus. However, while the physiological properties of the isolates were almost identical, pronounced physiological differences between the isolates and Sphaerotilus natans DSM 6575^T, DSM 565, and DSM 566 with respect to their ability to metabolize complex polysaccharides, sugars, polyalcohols, or organic acids as carbon sources were detected. In contrast to the analyzed culture collection strains of S. natans, all paper mill isolates were able to grow at elevated temperatures of up to 40°C. Comparative sequence analysis of nearly complete 16S ribosomal DNA (rDNA) sequences from the four new isolates demonstrated that the retrieved sequences were highly similar to each other (99.6 to 99.8% similarity) and to previously published partial 16S rDNA sequences of S. natans DSM 6575^T and ATCC 15291. Polyphasic characterization of the isolated Sphaerotilus strains revealed interesting adaptations of the strains to the environmental paper mill conditions with regard to temperature tolerance and utilization of cellulose and starch.