The interaction of environmental bacteria with unicellular eukaryotes is generally considered a major driving force for the evolution of intracellular pathogens, allowing them to survive and replicate in phagocytic cells of vertebrate hosts. To test this hypothesis on a genome-wide level, we determined for the intracellular pathogen Mycobacterium marinum whether it uses conserved strategies to exploit host cells from both protozoan and vertebrate origin. Using transposon-directed insertion site sequencing (TraDIS), we determined differences in genetic requirements for survival and replication in phagocytic cells of organisms from different kingdoms. In line with the general hypothesis, we identified a number of general virulence mechanisms, including the type VII protein secretion system ESX-1, biosynthesis of polyketide lipids, and utilization of sterols. However, we were also able to show that M. marinum contains an even larger set of host-specific virulence determinants, including proteins involved in the modification of surface glycolipids and, surprisingly, the auxiliary proteins of the ESX-1 system. Several of these factors were in fact counterproductive in other hosts. Therefore, M. marinum contains different sets of virulence factors that are tailored for specific hosts. Our data imply that although amoebae could function as a training ground for intracellular pathogens, they do not fully prepare pathogens for crossing species barriers.