The biodegradation of both an n-alkane and several carboxylated cycloalkanes was examined within tailings produced by the extraction of bitumen from the Athabasca oil sands. The carboxylated cycloalkanes examined were structurally similar to naphthenic acids that have been associated with the acute toxicity of oil sand tailings. The biodegradation potential of naphthenic acids was estimated by determining the biodegradation of both the carboxylated cycloalkanes and hexadecane in oil sand tailings. Carboxylated cycloalkanes were biodegraded within oil sand tailings, although compounds with methyl substitutions on the cycloalkane ring were more resistant to microbial degradation. Microbial activity against hexadecane and certain carboxylated cycloalkanes was found to be nitrogen and phosphorus limited.