Bacterial utilization of crude oil components, such as the n-alkanes, requires complex cell surface adaptation to allow adherence to oil. To better understand microbial cell surface adaptation to growth on crude oil, the cell surface characteristics of two Pseudomonas aeruginosa strains, U1 and U3, both isolated from the same crude oil-degrading microbial community enriched on Bonny Light crude oil (BLC), were compared. Analysis of growth rates demonstrated an increased lag time for U1 cells compared to U3 cells. Amendment with EDTA inhibited U1 and U3 growth and degradation of the n-alkane component of BLC, suggesting a link between cell surface structure and crude oil degradation. U1 cells demonstrated a smooth-to-rough colony morphology transition when grown on BLC, while U3 cells exhibited rough colony morphology at the outset. Combining high-resolution atomic force microscopy of the cell surface and sodium dodecyl sulfate-polyacrylamide gel electrophoresis of extracted lipopolysaccharides (LPS), we demonstrate that isolates grown on BLC have reduced O-antigen expression compared with that of glucose-grown cells. The loss of O-antigen resulted in shorter LPS molecules, increased cell surface hydrophobicity, and increased n-alkane degradation.