The 1976 outbreak of Legionnaires' disease led to the discovery of the intracellular bacterial pathogen Legionella pneumophila. Given their impact on human health, Legionella species and the mechanisms responsible for their replication within host cells are often studied in alveolar macrophages, the primary human cell type associated with disease. Despite the potential severity of individual cases of disease, Legionella are not spread from person-to-person. Thus, from the pathogen's perspective, interactions with human cells are accidents of time and space—evolutionary dead ends with no impact on Legionella's long-term survival or pathogenic trajectory. To understand Legionella as a pathogen is to understand its interaction with its natural hosts: the polyphyletic protozoa, a group of unicellular eukaryotes with a staggering amount of evolutionary diversity. While much remains to be understood about these enigmatic hosts, we summarize the current state of knowledge concerning Legionella's natural host range, the diversity of Legionella-protozoa interactions, the factors influencing these interactions, the importance of avoiding the generalization of protozoan-bacterial interactions based on a limited number of model hosts and the central role of protozoa to the biology, evolution, and persistence of Legionella in the environment.