Abstract Background Cancer cells undergo global reprogramming of cellular metabolism to satisfy demands of energy and biomass during proliferation and metastasis. Computational modeling of genome-scale metabolic models is an effective approach for designing new therapeutics targeting dysregulated cancer metabolism by identifying metabolic enzymes crucial for satisfying metabolic goals of cancer cells, but nearly all previous studies neglect the existence of metabolic demands other than biomass synthesis and trade-offs between these contradicting metabolic demands. It is thus necessary to develop computational models covering multiple metabolic objectives to study cancer metabolism and identify novel metabolic targets. Methods We developed a multi-objective optimization model for cancer cell metabolism at genome-scale and an integrated, data-driven workflow for analyzing the Pareto optimality of this model in achieving multiple metabolic goals and identifying metabolic enzymes crucial for maintaining cancer-associated metabolic phenotypes. Using this workflow, we constructed cell line-specific models for a panel of cancer cell lines and identified lists of metabolic targets promoting or suppressing cancer cell proliferation or the Warburg Effect. The targets were then validated using knockdown and over-expression experiments in cultured cancer cell lines. Results We found that the multi-objective optimization model correctly predicted phenotypes including cell growth rates, essentiality of metabolic genes and cell line specific sensitivities to metabolic perturbations. To our surprise, metabolic enzymes promoting proliferation substantially overlapped with those suppressing the Warburg Effect, suggesting that simply targeting the overlapping enzymes may lead to complicated outcomes. We also identified lists of metabolic enzymes important for maintaining rapid proliferation or high Warburg Effect while having little effect on the other. The importance of these enzymes in cancer metabolism predicted by the model was validated by their association with cancer patient survival and knockdown and overexpression experiments in a variety of cancer cell lines. Conclusions These results confirm this multi-objective optimization model as a novel and effective approach for studying trade-off between metabolic demands of cancer cells and identifying cancer-associated metabolic vulnerabilities, and suggest novel metabolic targets for cancer treatment. Graphical abstract