Stewardship programs providing financial incentives for conservation on private lands are increasingly common. We estimate the potential costs of a stewardship program in the Daly River catchment, Northern Territory, which would underwrite the cost difference between routine land management and the additional requirements of conservation management on grazing properties. Based on survey responses from landholders, we first assess the current costs of land management in the catchment and use regression to identify key drivers of spatial variation in both routine land management costs and conservation-oriented management costs. We define conservation-oriented management costs as the costs required to meet objectives for both routine property management and conservation. We then estimate the additional costs of conservation management over and above routine land management at an average of $1.99 per ha. We conclude that, if the most cost-effective properties are targeted, an annual budget of $1 million would support stewardship agreements covering 90% of the catchment’s area. Much of the cost-effectiveness of stewardship payments would come from the significant economies of scale in managing large pastoral properties and leveraging the costs of routine land management already met by landholders.