Phenazines are a class of bacterially produced redox-active metabolites that are found in natural, industrial, and clinical environments. In Pseudomonas spp., phenazine-1-carboxylic acid (PCA)-the precursor of all phenazine metabolites-facilitates nutrient acquisition, biofilm formation, and competition with other organisms. While the removal of phenazines negatively impacts these activities, little is known about the genes or enzymes responsible for phenazine degradation by other organisms. Here, we report that the first step of PCA degradation by Mycobacterium fortuitum is catalyzed by a phenazine-degrading decarboxylase (PhdA). PhdA is related to members of the UbiD protein family that rely on a prenylated flavin mononucleotide cofactor for activity. The gene for PhdB, the enzyme responsible for cofactor synthesis, is present in a putative operon with the gene encoding PhdA in a region of the M. fortuitum genome that is essential for PCA degradation. PhdA and PhdB are present in all known PCA-degrading organisms from the Actinobacteria. M. fortuitum can also catabolize other Pseudomonas-derived phenazines such as phenazine-1-carboxamide, 1-hydroxyphenazine, and pyocyanin. On the basis of our previous work and the current characterization of PhdA, we propose that degradation converges on a common intermediate: dihydroxyphenazine. An understanding of the genes responsible for degradation will enable targeted studies of phenazine degraders in diverse environments.