Systems analyses have facilitated the characterization of metabolic networks of several organisms. We have reconstructed the metabolic network of Leishmania major, a poorly characterized organism that causes cutaneous leishmaniasis in mammalian hosts. This network reconstruction accounts for 560 genes, 1112 reactions, 1101 metabolites and 8 unique subcellular localizations. Using a systems-based approach, we hypothesized a comprehensive set of lethal single and double gene deletions, some of which were validated using published data with approximately 70% accuracy. Additionally, we generated hypothetical annotations to dozens of previously uncharacterized genes in the L. major genome and proposed a minimal medium for growth. We further demonstrated the utility of a network reconstruction with two proof-of-concept examples that yielded insight into robustness of the network in the presence of enzymatic inhibitors and delineation of promastigote/amastigote stage-specific metabolism. This reconstruction and the associated network analyses of L. major is the first of its kind for a protozoan. It can serve as a tool for clarifying discrepancies between data sources, generating hypotheses that can be experimentally validated and identifying ideal therapeutic targets.