Road-infrastructure projects are expanding rapidly worldwide while penetrating into previously undisturbed forests. Such roads often lead to increased forest encroachment and illegal logging, fires, poaching, and mining. In Sumatra, Indonesia, a planned 88 km-long mining road for transporting coal would imperil the Harapan Forest, the island’s largest surviving tract of lowland rainforest. To evaluate the potential impact of the proposed road, we first manually mapped all existing roads inside and around the Harapan Forest using remote-sensing imagery. We then calculated the expected increase in forest loss from three proposed mining-road routes using a metric based on travel-time mapping. Finally, we used least-cost-path analyses, a strategic land-use planning method, to identify new routes for the road that would minimize forest disruption and road-construction costs. We found that road density inside and nearby the Harapan Forest is already 3-4 times higher than official data sources indicate. Based on our analyses, each of the three proposed mining-road routes would lead to 3,000-4,300 ha of additional forest loss from human encroachment on top of the reported 424 ha lost from road construction itself. Following the least-cost path analysis, we propose new routes for the mining road that would result in up to 3,321 ha less forest loss. Our alternative proposed routes also result in with markedly lower construction costs than any of the original planned routes. We recommend the use of strategic land-use planning methods, such as least-cost path analysis, to minimize the environmental and financial costs of major development projects.