Environmental policies that require native vegetation conservation can be challenging to implement, especially in productive agricultural landscapes. In Brazil, the Brazilian Native Vegetation Protection Law mandates ‘Legal Reserves’, protected native vegetation that landowners must retain on their properties. If landowners do not have the required minimum amount of native vegetation on their properties (the Legal Reserve ‘target’), they must either restore vegetation on the same property to meet the target, or compensate by protecting existing vegetation or restoring it on another property, ideally in ecologically equivalent areas. Here, we evaluate how different strategies (on-site/off-site protection and/or restoration), and different requirements for ecological equivalence when off-site strategies are used, affect the ability to achieve Legal Reserve targets, while minimising the need to restore native vegetation on productive farmland. We used a novel iterative tool to build scenarios that reflect different combinations of strategies to meet the minimum conservation target under different requirements for ecological equivalence, and compared their ability to achieve the target and their likely cost. The Atlantic Forest was the only biome where it was not possible to achieve the Legal Reserve target by protection of existing native vegetation, even when ecological equivalence rules were relaxed. As a consequence, vegetation restoration is required in this biome. Directing this required restoration to pasturelands that are less-suitable for agriculture allowed the target to be achieved in all states of Brazil, as long as only minimal ecological equivalence was required; however, for most states, the need to restore native vegetation on productive areas on farmlands could still be avoided while requiring medium to high ecological equivalence. These findings show the potential for moderate ecological equivalence to be achieved across most of Brazil in a cost-effective way and without impairing productive lands when seeking to meet the Legal Reserve targets.