In the wake of numerous sequenced genomes becoming available, computational methods for the reconstruction of metabolic networks have received considerable attention. Here, we review recent methods and software tools useful along the reconstruction workflow, from sequence annotation and network assembly to model verification and testing against experimental data. Reconstruction methods can be divided into three categories, depending on the magnitude of network context which is taken into account in the process of assembling the metabolic model: First, each enzyme may be predicted independently by annotation transfer or machine learning methods. Second, the presence of a metabolic pathway may be detected from genome and experimental evidence, often utilizing a reference pathway database. Third, the method may attempt to directly reconstruct a consistent metabolic network without relying on predefined reference pathways. Regardless of the chosen context, all methods strive to reconstruct genome-scale metabolic reconstructions. Currently a gap exists between software platforms dedicated to genome annotation and computational tools for automatically repairing network inconsistencies and validating against measurement data. We argue that to accelerate the reconstruction efforts, computational tools need to be developed that bridge the phases of the reconstruction workflow. In particular, the goal of finding consistent metabolic models suitable for computational analysis should be taken into account already in the beginning phases of reconstruction.