Biological treatment methods are the most important part of the treatment process for domestic wastewater, the amounts of which are increasing every year due to rapid, unregulated urbanization and the rising number of people living in such areas. At the same time, microorganisms existing in treatment facilities should not only effectively utilize organic pollutants, but also be resistant to a variety of organic and inorganic contaminants. This study’s objective is to isolate and identify—using molecular genetic techniques—strains of bacteria that tolerate concentrations of heavy metals (Ni, Cd, Pb, Zn and Cu) in the 3–5 mM range. They were sourced from water and sludge samples obtained from sewage treatment facilities in a large city. Outcomes of phylogenetic analysis of 16S rRNA gene sequences revealed that tolerant strains of bacteria belonged to the genera Pseudomonas, Serratia and Klebsiella; strains belonging to the genus Pseudomonas dominated. Of ten resistant strains, nine were isolated from sludge and water samples of the secondary sedimentation tank, and the other one from a treatment plant’s digester. Changes in the color of microorganisms’ colonies became evident when cultivated on media enriched with heavy metals. Cultivating nonpathogenic strains of these bacteria and their introduction into communities of other activated sludge microorganisms could have practical application to biological decontamination of wastewater.