The conservation of fold and chemistry of the enzymes associated with histidine biosynthesis suggests that this pathway evolved prior to the diversification of Bacteria, Archaea, and Eukaryotes. The only exception is the histidinol phosphate phosphatase (HolPase). So far, non-homologous HolPases that possess distinct folds and belong to three different protein superfamilies have been identified in various phylogenetic clades. However, their evolution has remained unknown to date. Here, we analyzed the evolutionary history of the HolPase from gamma-Proteobacteria (HisB-N). It has been argued that HisB-N and its closest homologue d-glycero-d-manno-heptose-1,7-bisphosphate 7-phosphatase (GmhB) have emerged from the same promiscuous ancestral phosphatase. GmhB variants catalyze the hydrolysis of the anomeric d-glycero-d-manno-heptose-1,7-bisphosphate (alpha HBP or beta HBP) with a strong preference for one anomer (alpha GmhB or beta GmhB). We found that HisB-N from Escherichia coli shows promiscuous activity for beta HBP but not alpha HBP, while beta GmhB from Crassaminicella sp. shows promiscuous activity for HolP. Accordingly, a combined phylogenetic tree of alpha GmhBs, beta GmhBs, and HisB-N sequences revealed that HisB-Ns form a compact subcluster derived from beta GmhBs. Ancestral sequence reconstruction and in vitro analysis revealed a promiscuous HolPase activity in the resurrected enzymes prior to functional divergence of the successors. The following increase in catalytic efficiency of the HolP turnover is reflected in the shape and electrostatics of the active site predicted by AlphaFold. An analysis of the phylogenetic tree led to a revised evolutionary model that proposes the horizontal gene transfer of a promiscuous beta GmhB from delta- to gamma-Proteobacteria where it evolved to the modern HisB-N.