Understanding the cost-effectiveness of restoration initiatives is critical for their successful implementation. In this context, this study presents a new approach to investigating the cost-effectiveness of different forest landscape restoration strategies for achieving multiple restoration goals. The approach is based on an optimization model that allocates forest restoration to maximize three environmental benefits (biodiversity conservation, carbon stock increase, and soil loss reduction) while minimizing the cost. We explore scenarios based on the Brazilian Forest Code and the National Policy for Payment for Ecosystem Services. Our optimization approach simultaneously achieves high levels of multiple environmental benefits - more than 90% of the maximum possible biodiversity, carbon, and soil in a cost-effective manner for all scenarios. Variation among the scenarios in the absolute performance concerning the three objectives was small (within 2.5%) compared to variation in costs (up to 19.4%). These results reinforce the importance of quantifying trade-offs among objectives to a better understanding of the cost-effectiveness of restoration initiatives before their implementation.