Protists kill their bacterial prey using toxic metals such as copper. Here we hypothesize that the metalloid arsenic has a similar role. To test this hypothesis, we examined intracellular survival of Escherichia coli (E. coli) in the amoeba Dictyostelium discoideum (D. discoideum). Deletion of the E. coli ars operon led to significantly lower intracellular survival compared to wild type E. coli. This suggests that protists use arsenic to poison bacterial cells in the phagosome, similar to their use of copper. In response to copper and arsenic poisoning by protists, there is selection for acquisition of arsenic and copper resistance genes in the bacterial prey to avoid killing. In agreement with this hypothesis, both copper and arsenic resistance determinants are widespread in many bacterial taxa and environments, and they are often found together on plasmids. A role for heavy metals and arsenic in the ancient predator–prey relationship between protists and bacteria could explain the widespread presence of metal resistance determinants in pristine environments.