The flavoenzyme NctB from Shinella sp. HZN7 catalyzes the oxidation of (S)-6-hydroxynicotine to 6-hydroxypseudooxynicotine concomitant with dioxygen reduction, which is the same chemistry catalyzed by the well-studied flavoenzyme L-6-hydroxynicotine oxidase (LHNO) from Paenarthrobacter nicotinovorans. However, while both enzymes are members of the flavoprotein amine oxidoreductase (FAO) family, they share only 26% sequence identity and are evolutionarily distant. Furthermore, nearly all FAOs (including LHNO) have a conserved lysine proximal to N5 of the flavin that is known to promote the reaction with O2 in the oxidative half-reaction, yet NctB, unusually, has a glutamate (Glu292) at this position. We report here using transient kinetics that NctB reacts rapidly with dioxygen in the oxidative half-reaction despite lacking the conserved lysine associated with promoting the reaction with O2 in FAO family enzymes. Mutagenesis reveals that a lysine derived from a different sequence position (Lys331) likely accelerates the reaction with dioxygen in NctB, as the K331M mutation results in a 1400-fold decrease in rate constant for reaction with O2. Glu292 forms a salt bridge with Lys331 in the structure of NctB, and a E292T mutation results in a ~80-fold decrease in rate constant for reaction with O2, suggesting that Glu292 optimizes the positioning and/or properties of Lys331 to promote dioxygen activation. Analysis of pH-rate effects in NctB shows similar pH profiles as in LHNO despite having differences in active site structure. These results indicate that NctB and LHNO convergently evolved to have the same enzymatic function.