Poaching is a global problem causing the decline of species worldwide. Optimizing the efficiency of ranger patrols to deter poaching activity at the lowest possible cost is crucial for protecting species with limited resources. We applied decision analysis and spatial optimization algorithms to allocate efforts of ranger patrols throughout a national park. Our objective was to mitigate poaching activity at or below management risk targets for the lowest monetary cost. We examined this trade‐off by constructing a Pareto efficiency frontier using integer linear programming. We used data from a ranger‐based monitoring program in Nyungwe National Park, Rwanda. Our measure of poaching risk is based on dynamic occupancy models that account for imperfect detection of poaching activities. We found that in order to achieve a 5% reduction in poaching risk, 622 ranger patrol events (each corresponding to patrolling 1‐km² sites) were needed within a year at a cost of US$49,760. In order to attain a 60% reduction in poaching risk, 15,560 patrol events were needed at a cost of US\$1,244,800. We evaluated the trade‐off between patrol cost and poaching risk based on our model by constructing a Pareto efficiency frontier and park managers found the solution for a 50% risk reduction to be a practical trade‐off based on funding constraints (comparable to recent years) and the diminishing returns between risk mitigation and cost. This expected reduction in risk required 8,558 patrol events per year at a cost of US \$684,640. Our results suggest that optimal solutions could increase efficiency compared to the actual effort allocations from 2006 to 2016 in Nyungwe National Park (e.g., risk reductions of ~30% under recent budgets compared to ~50% reduction in risk under the optimal strategy). The modeling framework in this study took into account imperfect detection of poaching risk as well as the directional and conditional nature of ranger patrol events given the spatial adjacency relationships of neighboring sites and access points. Our analyses can help to improve the efficiency of ranger patrols, and the modeling framework can be broadly applied to other spatial conservation planning problems with conditional, multilevel, site selection.