Three hydrocarbon-degrading psychrotrophic bacteria were isolated from petroleum-contaminated Arctic soils and characterized. Two of the strains, identified as Pseudomonas spp., degraded C5 to C12 n-alkanes, toluene, and naphthalene at both 5 and 25 degrees C and possessed both the alk catabolic pathway for alkane biodegradation and the nah catabolic pathway for polynuclear aromatic hydrocarbon biodegradation. One of these strains contained both a plasmid slightly smaller than the P. oleovorans OCT plasmid, which hybridized to an alkB gene probe, and a NAH plasmid similar to NAH7, demonstrating that both catabolic pathways, located on separate plasmids, can naturally coexist in the same bacterium.