The potential of graphene oxide (GO) in environmental applications, such as the development of antimicrobial materials and low-fouling membranes, has thus far been hindered by an incomplete understanding of bioadhesion mechanisms on GO interfaces. Using atomic force microscopy (AFM)-based single-cell force spectroscopy, we investigate the adhesion of single Pseudomonas fluorescens cells on GO-functionalized interfaces possessing distinct morphologies. Specifically, we investigate Si-GO surfaces, in which Langmuir–Blodgett GO films are transferred to Si wafers by dip-coating, forming an immobilized layer of horizontally arranged GO nanosheets, and PLL-GO surfaces, where GO nanosheets, edge-tethered to poly-l-lysine, form an interface characterized by morphological and conformational disorder. We observe strong adhesion forces on both Si-GO and PLL-GO surfaces; analysis of the pull-off forces in terms of the worm-like chain model reveals that adhesion is driven by hydrophobic interactions between proteinaceous adhesins on P. fluorescens and graphenic basal planes. We further show that adhesion forces are significantly stronger on Si-GO surfaces that facilitate interactions with graphenic planes, compared to PLL-GO surfaces, which show weaker adhesion due to steric and electrostatic repulsion. These results therefore demonstrate that the spatial orientation and conformational disorder of GO nanosheets are key factors governing the interfacial properties of graphene nanomaterials.