ABSTRACT Persistent infections require bacteria to evolve from their naïve colonization state by optimizing fitness in the host. This optimization involves coordinated adaptation of multiple traits, obscuring evolutionary trends and complicating infection management. Accordingly, we screen 8 infection-relevant phenotypes of 443 longitudinal Pseudomonas aeruginosa isolates from 39 young cystic fibrosis patients over 10 years. Using statistical modeling, we map evolutionary trajectories and identify trait correlations accounting for patient-specific influences. By integrating previous genetic analyses of 474 isolates, we provide a window into early adaptation to the host, finding: 1) a 2-3 year timeline of rapid adaptation after colonization, 2) variant “naïve” and “adapted” states reflecting discordance between phenotypic and genetic adaptation, 3) adaptive trajectories leading to persistent infection via 3 distinct evolutionary modes, and 4) new associations between phenotypes and pathoadaptive mutations. Ultimately, we effectively deconvolute complex trait adaptation, offering a framework for evolutionary studies and precision medicine in clinical microbiology.