Background: Flux Balance Analysis (FBA) is a widely used tool to model metabolic behavior and cellular function. Applications of FBA span a breadth of research from synthetic engineering of biofuels to understanding evolutionary adaptations. FBA predicts metabolic reaction fluxes that optimize a given objective. This objective is generally defined for unicellular organisms by a theoretical reaction which simulates biomass production. FBA has been extremely successful at predicting in E. coli growth rates under different media and gene essentiality, amongst other things. In order to improve predictions, additional constraints are coupled with optimization of the biomass function. Studies have suggested, however, that unicellular organisms - like multicellular organisms - do not grow at optimal rates. To further improve FBA predictions, particularly of internal cell fluxes, new techniques to explore the sub-optimal solution space need to be developed. Results: We present an innovative FBA method called corsoFBA based on the optimization of protein cost at sub-optimal objective levels. Our method shows good agreement with experimental data of E. coli grown at different dilution rates. Maintaining the objective function close to its maximum value predicts metabolic states that closely resemble low dilution rates; while higher dilution rates can be mirrored by lowering the biomass production value. By using a modified version of Extreme Pathways, we are also able to quantify the energy production and overall protein cost for all possible pathways in the central carbon metabolism. Conclusion: Metabolic flux distributions at the optimal objective can be substantially different from the near-optimal distributions. Importantly, the behavior of E. coli central carbon metabolism can be better predicted by exploring the sub-optimal FBA solution space. The corsoFBA method presented here is able to predict the behavior of PEP Carboxylase, the glyoxylate shunt and the Entner-Doudoroff pathway at different glucose levels, a behavior not predicted by the minimization of metabolic steps and FBA alone. This technique can be used to better predict internal cell fluxes under different conditions, and corsoFBA will be of great help for the study of cells from multicellular organisms using Flux Balance Analysis.