Two carbapenem-resistant isolates, one Escherichia coli isolate and one Klebsiella pneumoniae isolate, recovered from an Algerian patient expressed a novel VIM-type metallo-beta-lactamase (MBL). The identified bla(VIM-19) gene was located on a ca. 160-kb plasmid and located inside a class 1 integron in both isolates. VIM-19 differed from VIM-1 by the Asn215Lys and Ser228Arg substitutions, increasing its hydrolytic activity toward carbapenems. Site-directed mutagenesis experiments showed that both substitutions were necessary for the increased carbapenemase activity of VIM-19. This study indicates that MBLs with enhanced activity toward carbapenems may be obtained as a result of very few amino acid substitutions.