The amoeba Dictyostelium discoideum shares many traits with mammalian macrophages, in particular the ability to phagocytose and kill bacteria. In response, pathogenic bacteria use conserved mechanisms to fight amoebae and mammalian phagocytes. Here we developed an assay using Dictyostelium to monitor phagocyte-bacteria interactions. Genetic analysis revealed that the virulence of Klebsiella pneumoniae measured by this test is very similar to that observed in a mouse pneumonia model. Using this assay, two new host resistance genes (PHG1 and KIL1) were identified and shown to be involved in intracellular killing of K. pneumoniae by phagocytes. Phg1 is a member of the 9TM family of proteins, and Kil1 is a sulphotransferase. The loss of PHG1 resulted in Dictyostelium susceptibility to a small subset of bacterial species including K. pneumoniae. Remarkably, Drosophila mutants deficient for PHG1 also exhibited a specific susceptibility to K. pneumoniae infections. Systematic analysis of several additional Dictyostelium mutants created a two-dimensional virulence array, where the complex interactions between host and bacteria are visualized.