Little is known about how within-host evolution compares between genotypically different strains of the same pathogenic species. We sequenced the whole genomes of 474 longitudinally collected clinical isolates of Pseudomonas aeruginosa sampled from 34 children and young individuals with cystic fibrosis. Our analysis of 36 P. aeruginosa lineages identified convergent molecular evolution in 52 genes. This list of genes suggests a role in host adaptation for remodeling of regulatory networks and central metabolism, acquisition of antibiotic resistance and loss of extracellular virulence factors. Furthermore, we find an ordered succession of mutations in key regulatory networks. Accordingly, mutations in downstream transcriptional regulators were contingent upon mutations in upstream regulators, suggesting that remodeling of regulatory networks might be important in adaptation. The characterization of genes involved in host adaptation may help in predicting bacterial evolution in patients with cystic fibrosis and in the design of future intervention strategies.