The aim of this study was to screen for carbapenem-resistant Gram-negative bacteria in Palestine and subsequently to identify and investigate the mechanisms of resistance. For a period of 6 weeks, all Gram-negative isolates were collected from six Palestinian hospital laboratories and were tested for susceptibility using 10 μg meropenem disks. Isolates showing resistance to meropenem were further investigated. The presence of carbapenemases was assessed by PCR. In addition, antimicrobial susceptibility testing, an efflux pump inhibitor assay and pulsed-field gel electrophoresis (PFGE) were performed. Isolates producing carbapenemases were further investigated by multilocus sequence typing (MLST). In total, 248 Gram-negative isolates were collected from the six laboratories. Among the 248 tested isolates, 15 Acinetobacter baumannii and 6 Pseudomonas aeruginosa were resistant to meropenem. One A. baumannii from Gaza produced NDM-2 and belonged to ST103. Thirteen of the carbapenem-resistant A. baumannii isolates possessed the intrinsic upregulated blaOXA-66 gene and one isolate carried blaOXA-51. All but one of the OXA-66-producing A. baumannii belonged to ST2; the remaining isolate belonged to ST183. One of the carbapenem-resistant P. aeruginosa was classified as VIM-4-producing and three were VIM-2-producing isolates. The three VIM-2-producing isolates belonged to three new sequences types (ST1562, ST1563 and ST1564). All of the carbapenemase-producing isolates were multiresistant non-fermenters. To the best of our knowledge, this is the first report on NDM-producing A. baumannii and VIM-producing P. aeruginosa from Palestine.