Designing an optimal machine trail network is a complex locational problem that requires an understanding of different machines’ operations and terrain features as well as the trade-offs between various objectives. With the overall goal to minimize the operational costs of the logging operation, this paper proposes a mathematical optimization model for the trail network design problem and a greedy heuristic method based on different randomized search scenarios aiming to find the optimal location of machine trails —with potential to reduce negative environmental impact. The network is designed so that all trees can be reached and adapted to how the machines can maneuver while considering the terrain elevation’s influence. To examine the effectiveness and practical performance of the heuristic and the optimization model, it was applied in a case study on four harvest units with different topologies and shapes. The computational experiments show that the heuristic can generate solutions that outperform the solutions corresponding to conventional, manual designs within practical time limits for operational planning. Moreover, to highlight certain features of the heuristic and the parameter settings’ effect on its performance, we present an extensive computational sensitivity analysis.