Two toluene-degrading strains, T103 and T104, were isolated from rock surface biomass in a freshwater stream contaminated with toluene. The strains exhibit different capacities for degradation of toluene and other aromatic compounds and have characteristics of the genus Mycobacterium. Both are aerobic, rod-shaped, gram-positive, nonmotile, and acid-alcohol fast and produce yellow pigments. They have mainly straight-chain saturated and monounsaturated fatty acids with 10 to 20 carbon atoms and large amounts of tuberculostearic acid that are typical of mycobacteria. Fatty acid analyses indicate that T103 and T104 are different mycobacterial strains that are related at the subspecies level. Their identical 16S rDNA sequences are most similar to Mycobacterium aurum and Mycobacterium komossense, and they constitute a new species of fast-growing mycobacteria. Ecological studies reveal that toluene contamination has enriched for toluene-degrading bacteria in the epilithic microbial community. Strains T103 and T104 play only a small role in toluene degradation in the stream, although they are present in the habitat and can degrade toluene. Other microorganisms are consequently implicated in the biodegradation.