Bioremediation has been proposed as a means of dealing with oil spills on the continent. However, the introduction of non-native organisms, including microbes, even for this purpose would appear to breach the terms of the Environmental Protocol to the Antarctic Treaty. This study therefore aimed to optimize the growth conditions and diesel degradation activity of the Antarctic native bacteria Arthrobacter spp. strains AQ5-05 and AQ5-06 through the application of a one-factor-at-a-time (OFAT) approach. Both strains were psychrotolerant, with the optimum temperature supporting diesel degradation being 10–15°C. Both strains were also screened for biosurfactant production and biofilm formation. Their diesel degradation potential was assessed using Bushnell–Haas medium supplemented with 0.5% (v/v) diesel as the sole carbon source and determined using both gravimetric and gas chromatography and mass spectrophotometry analysis. Strain AQ5-06 achieved 37.5% diesel degradation, while strain AQ5-05 achieved 34.5% diesel degradation. Both strains produced biosurfactants and showed high biofilm adherence. Strains AQ5-05 and AQ5-06 showed high cellular hydrophobicity rates of 73.0% and 81.5%, respectively, in hexadecane, with somewhat lower values of 60.5% and 70.5%, respectively, in tetrahexadecane. Optimized conditions identified via OFAT increased diesel degradation to 41.0% and 47.5% for strains AQ5-05 and AQ5-06, respectively. Both strains also demonstrated the ability to degrade diesel in the presence of heavy metal co-pollutants. This study therefore confirms the potential use of these cold-tolerant bacterial strains in the biodegradation of diesel-polluted Antarctic soils at low environmental temperatures.