Colistin is an antimicrobial peptide that has become the only remaining alternative for the treatment of multidrug-resistant Gram-negative bacterial infections, but little is known of how clinical levels of colistin resistance evolve. We use in vitro experimental evolution and whole-genome sequencing of colistin-resistant Pseudomonas aeruginosa isolates from cystic fibrosis patients to reconstruct the molecular evolutionary pathways open for high-level colistin resistance. We show that the evolution of resistance is a complex, multistep process that requires mutation in at least five independent loci that synergistically create the phenotype. Strong intergenic epistasis limits the number of possible evolutionary pathways to resistance. Mutations in transcriptional regulators are essential for resistance evolution and function as nodes that potentiate further evolution towards higher resistance by functionalizing and increasing the effect of the other mutations. These results add to our understanding of clinical antimicrobial peptide resistance and the prediction of resistance evolution.