Annotation of organism-specific metabolic networks is one of the main challenges of systems biology. Importantly, due to inherent uncertainty of computational annotations, predictions of biochemical function need to be treated probabilistically. We present a global probabilistic approach to annotate genome-scale metabolic networks that integrates sequence homology and context-based correlations under a single principled framework. The developed method for Global Biochemical reconstruction Using Sampling (GLOBUS) not only provides annotation probabilities for each functional assignment, but also suggests likely alternative functions. GLOBUS is based on statistical Gibbs sampling of probable metabolic annotations and is able to make accurate functional assignments even in cases of remote sequence identity to known enzymes. We apply GLOBUS to genomes of Bacillus subtilis and Staphylococcus aureus, and validate the method predictions by experimentally demonstrating the 6-phosphogluconolactonase activity of ykgB and the role of the sps pathway for rhamnose biosynthesis in B. subtilis.