Genome-scale metabolic reconstructions (GEMs) are valuable resources for understanding and redesigning cellular networks as they encapsulate all the known biochemistry of the organisms from genes to proteins to their functions. Complexity of these large metabolic networks often hinders their utility in various practical applications. This difficulty calls for models of reduced sizes that are consistent with the genome-scale models. Currently available core models are reduced ad hoc with different aims and criteria, and up to date, there are no systematic reduction methods in the literature. In this work, we have developed redGEM, a systematic model reduction method for constructing core metabolic models from GEMs that is applicable to any genome-scale model. In redGEM, we use as inputs: (i) definition of the metabolic subsystems that are of interest for a physiology under study; (ii) information about the extracellular nutrients; and (iii) any available physiological data. Next, we employ a directed graph search method to find the connections between the selected subsystems, and we then apply a computational method to construct lumped reactions between the biomass building blocks and those subsystems. The result of this procedure is a reduced model that is consistent with the original GEM in terms of flux profiles and essential reactions. We applied the method to generate reduced models for the growth physiology of E. coli and S. cerevisiae under aerobic/anaerobic conditions.