Mussel adhesive proteins (MAPs) have been considered as potential underwater and medical bioadhesives. Previously, we reported a functional expression of recombinant MAP hybrid fp-151, which is a fusion protein with six type 1 (fp-1) decapeptide repeats at each type 5 (fp-5) terminus, with practical properties in Escherichia coli. In the present work, we introduced the Vitreoscilla hemoglobin (VHb) co-expression strategy to enhance the production levels of hybrid fp-151 since VHb has been successfully used for efficient oxygen utilization in several expression systems, including E. coli. In both batch-type flask and fed-batch-type bioreactor cultures, we found that co-expression of VHb conferred higher cell growth and hybrid fp-151 production. Its positive effects were significantly increased in high cell density bioreactor cultures as the microaerobic environment was more quickly and severely formed. We obtained a approximately 1.9-fold higher (approximately 1 g/L) production of MAP fp-151 from VHb co-expressing cells in fed-batch bioreactor cultures as compared to that from VHb non-expressing cells. Collectively and regardless of the culture type, VHb co-expression strategy was successful in enhancing the production of recombinant mussel adhesive proteins in the E. coli expression system.