p-Hydroxybenzoate hydroxylase (PHBH; EC 22.214.171.124) is a microbial group A flavoprotein monooxygenase that catalyzes the ortho-hydroxylation of 4-hydroxybenzoate to 3,4-dihydroxybenzoate with the stoichiometric consumption of NAD(P)H and oxygen. PHBH and related enzymes lack a canonical NAD(P)H-binding domain and the way they interact with the pyridine nucleotide coenzyme has remained a conundrum. Previously, we identified a surface exposed protein segment of PHBH from Pseudomonas fluorescens involved in NADPH binding. Here, we report the first amino acid sequences of NADH-preferring PHBHs and a phylogenetic analysis of putative PHBHs identified in currently available bacterial genomes. It was found that PHBHs group into three clades consisting of NADPH-specific, NAD(P)H-dependent and NADH-preferring enzymes. The latter proteins frequently occur in Actinobacteria. To validate the results, we produced several putative PHBHs in Escherichia coli and confirmed their predicted coenzyme preferences. Based on phylogeny, protein energy profiling and lifestyle of PHBH harboring bacteria we propose that the pyridine nucleotide coenzyme specificity of PHBH emerged through adaptive evolution and that the NADH-preferring enzymes are the older versions of PHBH. Structural comparison and distance tree analysis of group A flavoprotein monooxygenases indicated that a similar protein segment as being responsible for the pyridine nucleotide coenzyme specificity of PHBH is involved in determining the pyridine nucleotide coenzyme specificity of the other group A members.