Monitoring the emergence and transmission of Pseudomonas aeruginosa strains among cystic fibrosis (CF) patients is important for infection control in CF centers internationally. A recently developed multilocus sequence typing (MLST) scheme is used for epidemiologic analyses of P. aeruginosa outbreaks; however, little is known about its suitability for isolates from CF patients compared with that of pulsed-field gel electrophoresis (PFGE) and enterobacterial repetitive intergenic consensus-PCR (ERIC-PCR). As part of a prevalence study of P. aeruginosa strains in Australian CF clinics, we compared the discriminatory power and concordance of ERIC-PCR, PFGE, and MLST among 93 CF sputum and 11 control P. aeruginosa isolates. PFGE and MLST analyses were also performed on 30 paired isolates collected 85 to 354 days apart from 30 patients attending two CF centers separated by 3,600 kilometers in order to detect within-host evolution. Each of the three methods displayed high levels of concordance and discrimination; however, overall lower discrimination was seen with ERIC-PCR than with MLST and PFGE. Analysis of the 50 ERIC-PCR types yielded 54 PFGE types, which were related by ≤ 6 band differences, and 59 sequence types, which were classified into 7 BURST groups and 42 singletons. MLST also proved useful for detecting novel and known strains and for inferring relatedness among unique PFGE types. However, 47% of the paired isolates produced PFGE patterns that within 1 year differed by one to five bands, whereas with MLST all paired isolates remained identical. MLST thus represents a categorical analysis tool with resolving power similar to that of PFGE for typing P. aeruginosa. Its focus on highly conserved housekeeping genes is particularly suited for long-term clinical monitoring and detecting novel strains.