Nitrobenzene dioxygenase (NBDO) is known to add both atoms of molecular oxygen to the aromatic ring of nitrobenzene to form catechol. It is assembled by four subunits of which the alpha subunit is responsible for catalysis. As an oxidizing enzyme, it has a potential use in the detoxification of industrial waste and the synthesis of pharmaceuticals and food ingredients; however, not much work has been done studying its structure-function correlations. We used several protein engineering approaches (neutral drift libraries, random libraries, two types of focused libraries, and family shuffling) to engineer NBDO for the production of the highly potent antioxidant, hydroxytyrosol (HTyr), from the substrate 3-nitrophenethyl alcohol (3NPA). We obtained a triple mutant, F222C/F251L/G253D, which is able to oxidize 3NPA 375-fold better than wild type with a very high regioselectivity. In total, we identified four positions which are important for acquisition of new specificities, of which only one is well-known and studied. Based on homology modeling, it is suggested that these mutations increase activity by vacating extra space within the active site for the larger substrate and also by hydrogen bonding to the substrate. The best variant had acquired a stabilizing mutation which was beneficial only in this mutant. Thus, we have achieved two goals, the first is the enzymatic production of HTyr, and the second is valuable information regarding the structure-function correlations of NBDO.