Host colonization by Gram-negative pathogens often involves delivery of bacterial proteins called "effectors" into the host cell. The pneumonia-causing pathogen Legionella pneumophila delivers more than 330 effectors into the host cell via its type IVB Dot/Icm secretion system. The collective functions of these proteins are the establishment of a replicative niche from which Legionella can recruit cellular materials to grow while evading lysosomal fusion inhibiting its growth. Using a combination of structural, biochemical, and in vivo approaches, we show that one of these translocated effector proteins, Ceg4, is a phosphotyrosine phosphatase harboring a haloacid dehalogenase-hydrolase domain. Ceg4 could dephosphorylate a broad range of phosphotyrosine-containing peptides in vitro and attenuated activation of MAPK-controlled pathways in both yeast and human cells. Our findings indicate that L. pneumophila's infectious program includes manipulation of phosphorylation cascades in key host pathways. The structural and functional features of the Ceg4 effector unraveled here provide first insight into its function as a phosphotyrosine phosphatase, paving the way to further studies into L. pneumophila pathogenicity.