The metabolic engineering community relies on computational methods for pathway design to produce important small molecules in microbial hosts. Metabolic network databases are continuously curated and updated with known and novel reactions that expand the known biochemistry based on different sets of enzymatic reaction rules. To address the complexity of the metabolic networks, elaborate methods were developed to transform them into computable graphs, navigate them, and construct the best possible pathways. However, the recent experimental research points to the new challenges and opportunities for the computational pathway design. Here, we review the most recent advances, especially in the last two years, in computational discovery of new pathways and their prospects for expanding metabolic capabilities. We draw attention to the potential ways of improvement for pathway design algorithms, including the expansion of Design-Build-Test-Learn cycle to novel compounds and reactions and the standardization for the reaction rules and metabolic reaction databases.