Chronic Pseudomonas aeruginosa infections are the main cause of morbidity among patients with cystic fibrosis (CF) due to persistent lung inflammation caused by interaction between this bacterium and the immune system. Longitudinal studies of clonally related isolates of a dominant CF clone have indicated that genome reduction frequently occurs during adaptation of P. aeruginosa in the CF lung. In this study, we have evaluated the P. aeruginosa population structure of patients attending the Universitair Ziekenhuis Brussel (UZ Brussel) CF reference center using a combination of genotyping methods. Although the UZ Brussel P. aeruginosa CF population is characterized by the absence of a dominant CF clone, some potential interpatient transmissions could be detected. Interestingly, one of these clones showed deletion of the alternative type I ferripyoverdine receptor gene fpvB. Furthermore, we found that several other TonB-dependent receptors are deleted as well. The genome of one potentially transmissible CF clone was sequenced, revealing large deleted regions including all type III secretion system genes and several virulence genes. Remarkably, a large number of deleted genes are shared between the P. aeruginosa CF clone described in this study and isolates belonging to the dominant Copenhagen CF DK2 clone, suggesting parallel evolution.