Illegal, unreported and unregulated (IUU) fishing is a worldwide issue causing local and global financial losses, depleting natural resources and causing undue pressure upon the fishing industry. It is estimated that IUU fishing accounts for about 30% of all fishing activity worldwide, both on open oceans and within national exclusive economic zones. Responding to IUU fishing incidents is of paramount importance to law enforcement and marine environment protection organizations. We employ an optimization approach to the IUU problem by applying Evolutionary Multi-Objective Optimization solution techniques (EMOO) to automatically generate a set of promising candidate responses once an IUU fishing event has been identified. Four of the most frequently cited EMOO algorithms were used to explore the trade-off among three conflicting decision objectives, namely: the proximity to the IUU fishing vessel, the total cost of the response and the probability of confirming the detection, which is important for prosecution purposes.