Tackling illegal fishing through traditional state-centred approaches has proven difficult and largely ineffective in the extensive maritime environment of Southeast Asia, and particularly in the archipelagic state of Indonesia. This article focuses on the involvement of a new for-profit actor — a private tourism dive operator — in addressing illegal fishing in a small island archipelago in eastern Indonesia. The case study demonstrates that the dive operator has been able to employ conventional enforcement methods such as patrolling and the capture of illegal fishers, in combination with alternative approaches to addressing the root causes of illegal fishing. It also explores the relationship of the dive operator with civil society actors, non-governmental organizations (NGOs) and various state agencies involved in maritime security and conservation governance in the area. With a particular focus on the dive operator’s relationship with government agencies, the case study shows that local governments are collaborating with private actors and providing opportunities for new kinds of enforcement agents since they themselves lack sufficient resources to patrol waters effectively. The dive operator, however, operates only within a space granted by the district government, and must invest considerably in this relationship to maintain his position.