Large, long-lived marine animals (‘marine megafauna’) are amongst the world's most threatened taxa, primarily due to overfishing. Reducing fisheries' impacts on marine megafauna is particularly challenging in small-scale fisheries (SSFs), where endangered species can have important consumptive use values. Payments for ecosystem services (PES) have been proposed as a potential solution, but there is a lack of empirical data on if and how they might work in this context. We present a novel combination of methods – scenario interviews with contingent valuation (CV) – for exploring and designing locally-appropriate PES schemes; and apply these methods to investigate how different types of incentives might influence fisher behaviour and mortality of Critically Endangered taxa in two case study SSFs in Indonesia. Fishers almost unanimously supported positive conditional incentives: 98 % and 96 % of fishers would stop landing hammerhead sharks (Sphyrna spp.) and wedgefish (Rhynchobatus spp.), respectively, in contrast to 1 % and 6 % under a business-as-usual scenario, and 52 % and 46 % in response to a negative incentive (fine). CV results showed that an incentive-based scheme for catch mitigation of all hammerheads and wedgefish across both sites could cost US$71,408–235,927 annually, and save up to 18,500 and 2140 individuals, respectively. This study provides empirical evidence that PES could offer a cost-effective and socially-just approach for marine conservation in SSFs; and offers a scalable method for designing locally-appropriate investment-ready schemes, which could support the delivery of societal goals such as net positive outcomes for marine biodiversity and a sustainable and equitable blue economy.