Hydrogen fuel is renewable, efficient and clean, and fermentative bacteria hold great promise for its generation. Here we use the isogenic Escherichia coli K-12 KEIO library to rapidly construct multiple, precise deletions in the E. coli genome to direct the metabolic flux towards hydrogen production. Escherichia coli has three active hydrogenases, and the genes involved in the regulation of the formate hydrogen lyase (FHL) system for synthesizing hydrogen from formate via hydrogenase 3 were also manipulated to enhance hydrogen production. Specifically, we altered regulation of FHL by controlling the regulators HycA and FhlA, removed hydrogen consumption by hydrogenases 1 and 2 via the hyaB and hybC mutations, and re-directed formate metabolism using the fdnG, fdoG, narG, focA, fnr and focB mutations. The result was a 141-fold increase in hydrogen production from formate to create a bacterium (BW25113 hyaB hybC hycA fdoG/pCA24N-FhlA) that produces the largest amount of hydrogen to date and one that achieves the theoretical yield for hydrogen from formate. In addition, the hydrogen yield from glucose was increased by 50%, and there was threefold higher hydrogen production from glucose with this strain.