Ecological restoration is essential to curb the decline of biodiversity and ecosystems worldwide. Since the resources available for restoration are limited, restoration efforts must be cost-effective to achieve conservation outcomes. Although decision support tools are available to aid in the design of protected areas, little progress has been made to provide such tools for restoration efforts. Here, we introduce the restoptr R package, a decision support tool designed to identify priority areas for ecological restoration. It uses constraint programming—an artificial intelligence technique—to identify optimal plans given ecological and socioeconomic constraints. Critically, it can identify strategic locations to enhance connectivity and reduce fragmentation across a broader landscape using complex landscape metrics. We illustrate its usage with a case study in New Caledonia. By applying this tool, we identified priority areas for restoration that could reverse forest fragmentation induced by mining activities in a specific area. We also found that relatively small investments could deliver large returns to restore connectivity.