Pseudomonas aeruginosa is a major health concern globally and treating infections caused by MDR-isolates unarguably a humongous challenge that remains an unmet need in modern medicine. To determine patterns and mechanisms of antimicrobial resistance and its spread over the years in Rio de Janeiro, Brazil, 88 P. aeruginosa isolates were selected from 1995 to 2015. Phenotypic and genotypic characterization of antimicrobial resistance was evaluated and isolates were submitted to clonality by PFGE and MLST. PFGE analysis showed a great variability of clonal groups mainly over the past 10 years of this study. STs predominant in the early years (ST804, ST1860, ST487 and ST1602) associated to multidrug resistance (MDR) phenotype were replaced by ST277, ST244, ST1945, ST1791 with extensive drug resistance (XDR) in last years, with significant increase in resistance to carbapenems, fluoroquinolones and aminoglycosides. Colistin resistance was detected in 3.5%. The main mechanisms of antimicrobial resistance were mutational mechanisms (mutations in oprD, mexT and gyrA genes). We found the ESBL genes blaTEM (n = 2), blaSHV (n = 3) and blaCTX (n = 1).The carbapenemases genes was present in ST277 (blaSPM, n = 3), ST1560 (blaKPC, n = 3) and ST1944 (blaKPC, n = 2). The 16S RNA methylase gene (rmtD) was found in five isolates belonged to ST277. In conclusion, molecular epidemiological investigation reveals an increase of antimicrobial resistance in P. aeruginosa over 21 years in Rio de Janeiro with higher population structure and occurrence of high risk clone in the last years. The mutational mechanisms of resistance were present in all XDR isolates.