Ethanol production from whey powder was investigated by using free as well as alginate immobilized E. coli and E. coli expressing Vitreoscilla hemoglobin (VHb) in both shake flask and fermenter cultures. Media with varying levels of whey (lactose contents of 3%, 5%, 8% or 15%) and yeast extract (0.3% or 0.5%) were evaluated with fermentation times of 48–96 h. Immobilization and VHb expression resulted in higher ethanol production with all media; the increases ranged from 2% to 89% for immobilization and from 2% to 182% for VHb expression. It was determined that growth medium containing 8% lactose with 0.5% yeast extract yielded the highest ethanol production for free or immobilized strains, with or without VHb expression, in both shake flask and fermenter cultures. Immobilization with alginate was found to be a promising process for ethanol production by VHb-expressing ethanologenic E. coli.