Nicotine is a natural alkaloid produced by tobacco plants, and the mechanisms of its catabolism by microorganisms are diverse. In the present study, we reported the mutation, cloning, and identification of two novel genes involved in nicotine degradation from the newly isolated Pseudomonas sp. strain HZN6. Transposon mutagenesis identified a HZN6 mutant in which the nicotine-degrading pathway was blocked at pseudooxynicotine. A 3,874-bp DNA fragment flanking the transposon insertion site was obtained through self-formed adaptor PCR. Two open reading frames (designated pao and sap) were analyzed, and the deduced amino acid sequences shared 29% identity with 6-hydroxy-l-nicotine oxidase from Arthrobacter nicotinovorans and 49% identity with an aldehyde dehydrogenase from Bartonella henselae. Both pao and sap were cloned and functionally expressed in recombinant Escherichia coli BL21. The pao gene encoded a novel pseudooxynicotine amine oxidase with noncovalently bound flavin adenine dinucleotide (FAD) and exhibited substrate specificity removing the methylamine from pseudooxynicotine with the formation of 3-succinoylsemialdehyde-pyridine and hydrogen dioxide. The sap gene encoded a NADP(+)-dependent 3-succinoylsemialdehyde-pyridine dehydrogenase that catalyzed the dehydrogenation of 3-succinoylsemialdehyde-pyridine to 3-succinoyl-pyridine. Genetic analyses indicated that the pao gene played an essential role in nicotine or pseudooxynicotine mineralization in strain HZN6, whereas the sap gene did not. This study provides novel insight into the nicotine-degrading mechanism at the genetic level in Pseudomonas spp.