While designing synthetic adhesives that perform in aqueous environments has proven challenging, microorganisms commonly produce bioadhesives that efficiently attach to a variety of substrates, including wet surfaces. The aquatic bacterium Caulobacter crescentus uses a discrete polysaccharide complex, the holdfast, to strongly attach to surfaces and resist flow. The holdfast is extremely versatile and has impressive adhesive strength. Here, we used atomic force microscopy in conjunction with superresolution microscopy and enzymatic assays to unravel the complex structure of the holdfast and to characterize its chemical constituents and their role in adhesion. Our data support a model whereby the holdfast is a heterogeneous material organized as two layers: a stiffer nanoscopic core layer wrapped into a sparse, far-reaching, flexible brush layer. Moreover, we found that the elastic response of the holdfast evolves after surface contact from initially heterogeneous to more homogeneous. From a composition point of view, besides N-acetyl-d-glucosamine (NAG), the only component that had been identified to date, our data show that the holdfast contains peptides and DNA. We hypothesize that, while polypeptides are the most important components for adhesive force, the presence of DNA mainly impacts the brush layer and the strength of initial adhesion, with NAG playing a primarily structural role within the core. The unanticipated complexity of both the structure and composition of the holdfast likely underlies its versatility as a wet adhesive and its distinctive strength. Continued improvements in understanding of the mechanochemistry of this bioadhesive could provide new insights into how bacteria attach to surfaces and could inform the development of new adhesives.