Autophagy plays a key role during Salmonella infection, by eliminating these pathogens following escape into the cytosol. In this process, selective autophagy receptors, including the myosin VI adaptor proteins optineurin and NDP52, have been shown to recognize cytosolic pathogens. Here, we demonstrate that myosin VI and TAX1BP1 are recruited to ubiquitylated Salmonella and play a key role in xenophagy. The absence of TAX1BP1 causes an accumulation of ubiquitin-positive Salmonella, whereas loss of myosin VI leads to an increase in ubiquitylated and LC3-positive bacteria. Our structural studies demonstrate that the ubiquitin-binding site of TAX1BP1 overlaps with the myosin VI binding site and point mutations in the TAX1BP1 zinc finger domains that affect ubiquitin binding also ablate binding to myosin VI. This mutually exclusive binding and the association of TAX1BP1 with LC3 on the outer limiting membrane of autophagosomes may suggest a molecular mechanism for recruitment of this motor to autophagosomes. The predominant role of TAX1BP1, a paralogue of NDP52, in xenophagy is supported by our evolutionary analysis, which demonstrates that functionally intact NDP52 is missing in Xenopus and mice, whereas TAX1BP1 is expressed in all vertebrates analysed. In summary, this work highlights the importance of TAX1BP1 as a novel autophagy receptor in myosin VI-mediated xenophagy. Our study identifies essential new machinery for the autophagy-dependent clearance of Salmonella typhimurium and suggests modulation of myosin VI motor activity as a potential therapeutic target in cellular immunity.