We report on the design and implementation of ecological monitoring for an Australian biodiversity conservation incentive scheme - the Environmental Stewardship Program. The Program uses competitive auctions to contract individual land managers for up to 15 years to conserve matters of National Environmental Significance (with an initial priority on nationally threatened ecological communities). The ecological monitoring was explicitly aligned with the Program's policy objective and desired outcomes and was applied to the Program's initial Project which targeted the critically endangered White Box-Yellow Box-Blakely's Red Gum Grassy Woodland and Derived Native Grassland ecological community in south eastern Australia. These woodlands have been reduced to <3% of their original extent and persist mostly as small remnants of variable condition on private farmland. We established monitoring sites on 153 farms located over 172,232 sq km. On each farm we established a monitoring site within the woodland patch funded for management and, wherever possible, a matched control site. The monitoring has entailed gathering data on vegetation condition, reptiles and birds. We also gathered data on the costs of experimental design, site establishment, field survey, and data analysis. The costs of monitoring are approximately 8.5% of the Program's investment in the first four years and hence are in broad accord with the general rule of thumb that 5-10% of a program's funding should be invested in monitoring. Once initial monitoring and site benchmarking are completed we propose to implement a novel rotating sampling approach that will maintain scientific integrity while achieving an annual cost-efficiency of up to 23%. We discuss useful lessons relevant to other monitoring programs where there is a need to provide managers with reliable early evidence of program effectiveness and to demonstrate opportunities for cost-efficiencies.