Diverse bacteria, including several Pseudomonas species, produce a class of redox-active metabolites called phenazines that impact different cell types in nature and disease. Phenazines can affect microbial communities in both positive and negative ways, where their presence is correlated with decreased species richness and diversity. However, little is known about how the concentration of phenazines is modulated in situ and what this may mean for the fitness of members of the community. Through culturing of phenazine-degrading mycobacteria, genome sequencing, comparative genomics, and molecular analysis, we identified several conserved genes that are important for the degradation of three Pseudomonas-derived phenazines: phenazine-1-carboxylic acid (PCA), phenazine-1-carboxamide (PCN), and pyocyanin (PYO). PCA can be used as the sole carbon source for growth by these organisms. Deletion of several genes in Mycobacterium fortuitum abolishes the degradation phenotype, and expression of two genes in a heterologous host confers the ability to degrade PCN and PYO. In cocultures with phenazine producers, phenazine degraders alter the abundance of different phenazine types. Not only does degradation support mycobacterial catabolism, but also it provides protection to bacteria that would otherwise be inhibited by the toxicity of PYO. Collectively, these results serve as a reminder that microbial metabolites can be actively modified and degraded and that these turnover processes must be considered when the fate and impact of such compounds in any environment are being assessed. IMPORTANCE Phenazine production by Pseudomonas spp. can shape microbial communities in a variety of environments ranging from the cystic fibrosis lung to the rhizosphere of dryland crops. For example, in the rhizosphere, phenazines can protect plants from infection by pathogenic fungi. The redox activity of phenazines underpins their antibiotic activity, as well as providing pseudomonads with important physiological benefits. Our discovery that soil mycobacteria can catabolize phenazines and thereby protect other organisms against phenazine toxicity suggests that phenazine degradation may influence turnover in situ. The identification of genes involved in the degradation of phenazines opens the door to monitoring turnover in diverse environments, an essential process to consider when one is attempting to understand or control communities influenced by phenazines.