Like several other intracellular pathogens, Mycobacterium marinum (Mm) escapes from phagosomes into the host cytosol where it can polymerize actin, leading to motility that promotes spread to neighboring cells. However, only ∼25% of internalized Mm form actin tails, and the fate of the remaining bacteria has been unknown. Here we show that cytosolic access results in a new and intricate host pathogen interaction: host macrophages ubiquitinate Mm, while Mm shed their ubiquitinated cell walls. Phagosomal escape and ubiquitination of Mm occured rapidly, prior to 3.5 hours post infection; at the same time, ubiquitinated Mm cell wall material mixed with host-derived dense membrane networks appeared in close proximity to cytosolic bacteria, suggesting cell wall shedding and association with remnants of the lysed phagosome. At 24 hours post-infection, Mm that polymerized actin were not ubiquitinated, whereas ubiquitinated Mm were found within LAMP-1–positive vacuoles resembling lysosomes. Though double membranes were observed which sequestered Mm away from the cytosol, targeting of Mm to the LAMP-1–positive vacuoles was independent of classical autophagy, as demonstrated by absence of LC3 association and by Atg5-independence of their formation. Further, ubiquitination and LAMP-1 association did not occur with mutant avirulent Mm lacking ESX-1 (type VII) secretion, which fail to escape the primary phagosome; apart from its function in phagosome escape, ESX-1 was not directly required for Mm ubiquitination in macrophages or in vitro. These data suggest that virulent Mm follow two distinct paths in the cytosol of infected host cells: bacterial ubiquitination is followed by sequestration into lysosome-like organelles via an autophagy-independent pathway, while cell wall shedding may allow escape from this fate to permit continued residence in the cytosol and formation of actin tails.