Orthologs typically retain the same function in the course of evolution. Using β-decarboxylating dehydrogenase family as a model, we demonstrate that orthologs can be confidently identified. The strategy is based on our recent findings that substitutions of only a few amino acid residues in these enzymes are sufficient to exchange substrate and coenzyme specificities. Hence, the few major specificity determinants can serve as reliable markers for determining orthologous or paralogous relationships. The power of this approach has been demonstrated by correcting similarity-based functional misassignment and discovering new genes and related pathways, and should be broadly applicable to other enzyme families.