The toxicity of N-nitrosamines, their presence in drinking and environmental water supplies, and poorly understood recalcitrance collectively necessitate a better understanding of their potential for bioattenuation. Here, we show that the bacterial strain Rhodococcus jostii RHA1 can biotransform N-nitrosodiethylamine (NDEA), N-nitrosodi-n-propylamine (NDPA), N-nitrosopyrrolidine (NPYR), and possibly N-nitrosomorpholine (NMOR) in addition to N-nitrosodimethylamine (NDMA). Growth of cells on propane as the sole carbon source greatly enhanced degradation rates when contrasted with cells grown on complex organics. Propane-induced rates in order of fastest to slowest were NDMA > NDEA > NDPA > NPYR > NMOR at concentrations <2000 μg/L. Removal rates for linear functional groups scaled inversely with mass and cyclic nitrosamines were more recalcitrant than linear nitrosamines. Controls demonstrated significant NDEA and NDPA losses independent of biomass, suggesting abiotic processes may play a role in attenuation of these two compounds under experimental conditions tested here. In contrast to NDMA, a transition from first to zero order kinetics was not observed for the other nitrosamines included in this study over a concentration range of 20-2000 μg/L. A genetic knockout for the propane monooxygenase enzyme (PrMO) confirmed the role of this enzyme in the biotransformation of NDEA and NPYR. This study furthers our understanding of environmental nitrosamine attenuation by revealing an enzymatic mechanism for the biotransformation of multiple nitrosamines, their relative recalcitrance to transformation, and potential for abiotic loss.