This study concerns the potential use of Pseudomonas aeruginosa expressing the Vitreoscilla hemoglobin gene for the degradation of important harmful aromatic compounds such as benzene, toluene, and xylene (BTX). The use of these compounds by both strains was determined as the production of cell mass (viable cell number) in a minimal medium containing any one of the BTX compounds as the sole carbon and energy source. Furthermore, the BTX degradation capability of both strains was monitored by measuring the production of 3-methylcatechol, a common intermediate. For the cells of the logarithmic phase, which were grown at high aeration/high agitation or low aeration/low agitation, the engineered strain showed a better growth rate than the host strain. With the benzene in the medium, the recombinant strain exhibited a higher (up to 4-fold) cell density than the parental wild-type strain at this phase. In contrast, regarding the cells of the late stationary phase under high aeration/high agitation conditions, the host strain had generally higher viable cell numbers than the recombinant strain. At this phase this difference was, however, less significant under the conditions of low aeration/low agitation. Similarly, in toluene containing medium (at high aeration/high agitation) the recombinant strain showed a higher cell density which was from a 15-fold to almost one order of magnitude greater than its parental strain during the logarithmic phase where the cell density of P aeruginosa remained nearly constant. Contrary to the results with benzene and toluene, both strains exhibited similar growth characteristics when they were grown in the presence of xylene. The positive effect of the oxygen uptake by the recombinant system on the BTX metabolizing activity was also apparent in a high accumulation of 3-methylcatechol in the cultures of the recombinant strain. At certain points of incubation, the hemoglobin expressing strain showed a significantly (p < 0.05) higher 3-methylcatechol accumulation than the host strain. These results demonstrated the possible potential of the Vitreoscilla hemoglobin as an efficient oxygen uptake system for the bioremediation of some compounds of environmental concern.