Using multigenerational, single-cell tracking we explore the earliest events of biofilm formation by Pseudomonas aeruginosa. During initial stages of surface engagement (≤20 h), the surface cell population of this microbe comprises overwhelmingly cells that attach poorly (∼95% stay <30 s, well below the ∼1-h division time) with little increase in surface population. If we harvest cells previously exposed to a surface and direct them to a virgin surface, we find that these surface-exposed cells and their descendants attach strongly and then rapidly increase the surface cell population. This “adaptive,” time-delayed adhesion requires determinants we showed previously are critical for surface sensing: type IV pili (TFP) and cAMP signaling via the Pil-Chp-TFP system. We show that these surface-adapted cells exhibit damped, coupled out-of-phase oscillations of intracellular cAMP levels and associated TFP activity that persist for multiple generations, whereas surface-naïve cells show uncorrelated cAMP and TFP activity. These correlated cAMP–TFP oscillations, which effectively impart intergenerational memory to cells in a lineage, can be understood in terms of a Turing stochastic model based on the Pil-Chp-TFP framework. Importantly, these cAMP–TFP oscillations create a state characterized by a suppression of TFP motility coordinated across entire lineages and lead to a drastic increase in the number of surface-associated cells with near-zero translational motion. The appearance of this surface-adapted state, which can serve to define the historical classification of “irreversibly attached” cells, correlates with family tree architectures that facilitate exponential increases in surface cell populations necessary for biofilm formation.