Pseudomonas aeruginosa can cause life-threatening infections in immunocompromised patients. The first-line agents to treat P. aeruginosa infections are carbapenems. However, the emergence of carbapenem-resistant P. aeruginosa strains greatly compromised the effectiveness of carbapenem treatment, which makes the surveillance on their spreading and transmission important. Here we characterized the full-length genomes of two carbapenem-resistant P. aeruginosa clinical isolates that are capable of producing New Delhi metallo-β-lactamase-1 (NDM-1). We show that bla_NDM-1 is carried by a novel integrative and conjugative element (ICE) ICE_Tn43716385, which also carries the macrolide resistance gene msr(E) and the florfenicol resistance gene floR. By exogenously expressing msr(E) in P. aeruginosa laboratory strains, we show that Msr(E) can abolish azithromycin-mediated quorum sensing inhibition in vitro and anti-Pseudomonas effect in vivo. We conclude that ICEs are important in transmitting carbapenem resistance, and that anti-virulence treatment of P. aeruginosa infections using sub-inhibitory concentrations of macrolides can be challenged by horizontal gene transfer.