Antibiotic resistance is an alarming problem throughout the world and carbapenem-resistant Pseudomonas aeruginosa has been cataloged as critical in the World Health Organization list of microorganisms in urgent need for the development of new antimicrobials. In this work, we describe two novel resistance regions responsible for conferring a multidrug resistance phenotype to two clinical isolates of P. aeruginosa (Pa873 and Pa6415) obtained from patients hospitalized in the ICU of University Hospital of Uruguay. Bacterial identification and antibiotic susceptibility tests were performed using MALDI-TOF and the Vitek 2 system, respectively. WGS was performed for both isolates using Oxford Nanopore Technologies and Illumina and processed by means of hybrid assembly. Both isolates were resistant to ceftazidime, cefepime, piperacillin–tazobactam, aztreonam, and imipenem. Strain Pa6415 also showed resistance to ciprofloxacin. Both strains displayed MICs below the susceptibility breakpoint for CAZ-AVI plus 4 mg/L of aztreonam as well as cefiderocol. Both resistance regions are flanked by the left and right inverted repeats of ISPa40 in two small regions spanning 39.3 and 35.6 kb, for Pa6415 and Pa873, respectively. The resistance region of Pa6415 includes TnaphA6, and the new Tn7516 consists of IRi, In899, qacEΔ1-sul1-ISCR1, qnrVC6-ISCR1-blaPER-1-qacEΔ1-sul1, araJ-like, IS481-like tnpA, ISPa17, and IRR. On the other hand, the resistance region of Pa873 includes Tnaph6 and the new Tn7517 (IRi, In899, qacEΔ1-sul1, ISCR1–blaPER-1–qacEΔ1-sul1, araJ-like, IS481-like tnpA, ISPa17, and IRR). It is necessary to monitor the emergence of genetic structures that threaten to invalidate the available therapeutic resources.