Despite intensive antibiotic treatment, Pseudomonas aeruginosa often persists in the airways of cystic fibrosis (CF) patients for decades, and can do so without antibiotic resistance development. Using high-throughput screening assays of bacterial survival after treatment with high concentrations of ciprofloxacin, we have determined the prevalence of persisters in a large patient cohort using 460 longitudinal isolates of P. aeruginosa from 39 CF patients. Isolates were classed as high persister variants (Hip) if they regrew following antibiotic treatment in at least 75% of the experimental replicates. Strain genomic data, isolate phenotyping, and patient treatment records were integrated in a lineage-based analysis of persister formation and clinical impact. In total, 19% of the isolates were classified as Hip and Hip emergence increased over lineage colonization time within 22 Hip+ patients. Most Hip+ lineages produced multiple Hip isolates, but few Hip+ lineages were dominated by Hip. While we observed no strong signal of adaptive genetic convergence within Hip isolates, they generally emerged in parallel or following the development of ciprofloxacin resistance and slowed growth. Transient lineages were majority Hip-, while strains that persisted over a clinically diagnosed 'eradication' period were majority Hip+. Patients received indistinguishable treatment regimens before Hip emergence, but Hip+ patients overall were treated significantly more than Hip- patients, signaling repeated treatment failure. When subjected to in vivo-similar antibiotic dosing, a Hip isolate survived better than a non-Hip in a structured biofilm environment. In sum, the Hip phenotype appears to substantially contribute to long-term establishment of a lineage in the CF lung environment. Our results argue against the existence of a single dominant molecular mechanism underlying bacterial antibiotic persistence. We instead show that many routes, both phenotypic and genetic, are available for persister formation and consequent increases in strain fitness and treatment failure in CF airways.