Persistent infections require bacteria to evolve from their naïve colonization state by optimizing fitness in the host via simultaneous adaptation of multiple traits, which can obscure evolutionary trends and complicate infection management. Accordingly, here 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 three 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.