Bacteriophages and protists are major causes of bacterial mortality. Genomics suggests that phages evolved well before eukaryotic protists. Bacteria were thus initially only confronted with phage predators. When protists evolved, bacteria were caught between two types of predators. One successful antigrazing strategy of bacteria was the elaboration of toxins that would kill the grazer. The released cell content would feed bystander bacteria. I suggest here that, to fight grazing protists, bacteria teamed up with those phage predators that concluded at least a temporary truce with them in the form of lysogeny. Lysogeny was perhaps initially a resource management strategy of phages that could not maintain infection chains. Subsequently, lysogeny might have evolved into a bacterium-prophage coalition attacking protists, which became a food source for them. When protists evolved into multicellular animals, the lysogenic bacteria tracked their evolving food source. This hypothesis could explain why a frequent scheme of bacterial pathogenicity is the survival in phagocytes, why a significant fraction of bacterial pathogens have prophage-encoded virulence genes, and why some virulence factors of animal pathogens are active against unicellular eukaryotes. Bacterial pathogenicity might thus be one playing option of the stone-scissor-paper game played between phages-bacteria-protists, with humans getting into the crossfire.