Pseudomonas aeruginosa is a prominent bacterial pathogen that causes several nosocomial infections and is notorious for its environmental resilience and rapid development of resistance to frontline antibiotics. A major cause of mortality and morbidity among cystic fibrosis patients, multidrug-resistant P. aeruginosa is often targeted with the antibiotic colistin as a last option. However, increasing reports of colistin resistance among P. aeruginosa is a significant concern. Though the molecular mechanisms responsible for the development of colistin resistance are well known, the evolutionary trajectory to colistin resistance is an important area of investigation. In this work, using the adaptive laboratory evolution (ALE) approach we have evolved a colistin-sensitive P. aeruginosa ancestral strain to a resistant one. During the process of laboratory evolution in 106 generations, colistin MIC was increased 32-fold. The evolved strain had lower fitness than the ancestral strain, as evidenced by a lower growth rate. Moreover, the evolved strain produced more biofilm and less pyocyanin pigment. Interestingly, the evolved strain showed collateral sensitivity to several antibiotics, including ampicillin, tetracycline, streptomycin, gentamycin, nalidixic acid, trimethoprim, rifampicin, and chloramphenicol. On analysing various TCS modules involved in the development of colistin resistance, a novel missense mutation (V136G) was detected in the PmrB sensor kinase. In silico analysis indicated that the V136G substitution would destabilize the PmrB kinase structure, making the mutation deleterious. However, the functionality of the PmrB mutant remains to be validated experimentally.