The metabolically versatile Gram-negative bacterium Pseudomonas aeruginosa inhabits terrestrial, aquatic, animal-, human-, and plant-host-associated environments and is an important causative agent of nosocomial infections, particularly in intensive-care units. The population genetics of P. aeruginosa was investigated by an approach that is generally applicable to the rapid, robust, and informative genotyping of bacteria. DNA, amplified from the bacterial colony by circles of multiplex primer extension, is hybridized onto a microarray to yield an electronically portable binary multimarker genotype that represents the core genome by single nucleotide polymorphisms and the accessory genome by markers of genomic islets and islands. The 240 typed P. aeruginosa strains of diverse habitats and geographic origin segregated into two large nonoverlapping clusters and 45 isolated clonal complexes with few or no partners. The majority of strains belonged to few dominant clones widespread in disease and environmental habitats. The most frequent genotype was represented by the sequenced strain PA14. Core and accessory genome were found to be nonrandomly assembled in P. aeruginosa. Individual clones preferred a specific repertoire of accessory segments. Even the most promiscuous genomic island, pKLC102, had integrated preferentially into a subset of clones. Moreover, some physically distant loci of the core genome, including oriC, showed nonrandom associations of genotypes, whereas other segments in between were freely recombining. Thus, the P. aeruginosa genome is made up of clone-typical segments in core and accessory genome and of blocks in the core with unrestricted gene flow in the population.