This paper uses an actor-network perspective on innovation to examine the introduction of a mandatory product-oriented environmental management system (in Dutch: Product en MilieuZorg or PMZ) for Dutch outbound tour operators by the Netherlands Association of Tour Operators (VRO). In-depth interviews and a quantitative analysis of the actions taken by 126 outbound tour operators revealed that the introduction of the PMZ was extensively negotiated. The results show the various stages of implementation and three types of tour operators: `unconvinced minor participants¿, `open-minded yet sceptical participants¿, and `loyal actors¿. The analysis also demonstrates that on average, tour operators made 13.6 actions, which is almost three times the minimum requirement (five) set by the VRO. Between them, the 126 tour operators have undertaken a total of 1710 actions, of which over 87% concern the environmental dimension of sustainability. Unquestionably, the introduction of PMZ helped tour operators to identify some of the environmental consequences of their operations, and to single out and implement environmental friendly initiatives. However, the rather general criteria and lax entry requirements at this stage led to an abundance of proposed actions by tour operators that were often `soft¿ and indeterminate. New rounds of translations are necessary to maintain the momentum.