Enzymes of the ubiquitous flavoprotein amine oxidoreductase (FAO) superfamily catalyze C-N bond oxidation of amine-containing substrates using flavin adenine dinucleotide (FAD) as a prosthetic group. Their reaction proceeds via a two-step mechanism involving hydride transfer from the substrate to the bound FAD cofactor, and the reduced flavin is subsequently reoxidized by a physiological electron acceptor. For nearly a century, it has been generally accepted that all enzymes in the FAO superfamily are oxidases, i.e., donating the electrons from substrate oxidation to dioxygen (O2). However, we recently showed that the FAO family enzymes nicotine oxidoreductase and pseudooxynicotine amine oxidase are not oxidases because they do not utilize oxygen efficiently, and instead are cytochrome c utilizing dehydrogenases. Here we characterized other bacterial FAOs and show that many are actually dehydrogenases that react poorly with O2 in favor of using a cytochrome c (CytC) protein closely encoded in the genome, indicating that there are many exceptions to the oxidase paradigm that has been traditionally ascribed to the FAO superfamily. These dehydrogenases are highly specific for the CytC from the same organism and are phylogenetically clustered with other FAOs that appear to be oxidases. Our findings further undermine the long-held view that all FAO family enzymes are oxidases and suggest that evolutionary switches between different oxidants are surprisingly frequent in this enzyme family.