Sustainability and efficiency are potentially conflicting social objectives in natural resource management. We propose a market mechanism to allocate use rights over a stochastic resource to private managers. The mechanism endogenously determines the maximal tenure length guaranteeing that the sustainability goal is obeyed for sure over the entire period. In addition, the mechanism achieves efficiency, i.e. it maximizes the expected present value of resource rents that accrue to society. Potential applications include improved fishing agreements between developing countries and distant-water fishing fleets.