Using genome-wide mutant fitness assays in diverse bacteria, we identified novel oxidative pathways for the catabolism of 2-deoxy-d-ribose and 2-deoxy-d-ribonate. We propose that deoxyribose is oxidized to deoxyribonate, oxidized to ketodeoxyribonate, and cleaved to acetyl coenzyme A (acetyl-CoA) and glyceryl-CoA. We have genetic evidence for this pathway in three genera of bacteria, and we confirmed the oxidation of deoxyribose to ketodeoxyribonate in vitro. In Pseudomonas simiae, the expression of enzymes in the pathway is induced by deoxyribose or deoxyribonate, while in Paraburkholderia bryophila and in Burkholderia phytofirmans, the pathway proceeds in parallel with the known deoxyribose 5-phosphate aldolase pathway. We identified another oxidative pathway for the catabolism of deoxyribonate, with acyl-CoA intermediates, in Klebsiella michiganensis. Of these four bacteria, only P. simiae relies entirely on an oxidative pathway to consume deoxyribose. The deoxyribose dehydrogenase of P. simiae is either nonspecific or evolved recently, as this enzyme is very similar to a novel vanillin dehydrogenase from Pseudomonas putida that we identified. So, we propose that these oxidative pathways evolved primarily to consume deoxyribonate, which is a waste product of metabolism. IMPORTANCE Deoxyribose is one of the building blocks of DNA and is released when cells die and their DNA degrades. We identified a bacterium that can grow with deoxyribose as its sole source of carbon even though its genome does not contain any of the known genes for breaking down deoxyribose. By growing many mutants of this bacterium together on deoxyribose and using DNA sequencing to measure the change in the mutants’ abundance, we identified multiple protein-coding genes that are required for growth on deoxyribose. Based on the similarity of these proteins to enzymes of known function, we propose a 6-step pathway in which deoxyribose is oxidized and then cleaved. Diverse bacteria use a portion of this pathway to break down a related compound, deoxyribonate, which is a waste product of metabolism. Our study illustrates the utility of large-scale bacterial genetics to identify previously unknown metabolic pathways.