In recent years, many palm oil companies have committed to eliminating deforestation activities from their operations. NGO reports and companies’ self-identified challenges indicate that barriers exist that impede the implementation of these commitments. Here we show that complexity across the extent of the palm oil supply chain poses a major barrier that hinders companies from being able to secure guaranteed no-deforestation commitments. Other barriers include the lack of consensus on definitions of deforestation, inadequate government support and persisting markets for unsustainably-produced palm oil in China and India, which undermine companies’ efforts to achieve supplier engagement and compliance. Current certification standards, meanwhile, require amendment to help overcome barriers posed by supply chain complexity. In conclusion, the existing model used to address palm oil-driven deforestation, based on NGO shaming campaigns and unilateral adoption of commitments by individual companies, is unlikely to achieve no deforestation in the current context of palm oil production and trade. Instead, a broader set of complementary mechanisms is required to overcome supply chain complexity and ensure that no-deforestation commitments can be implemented successfully.