There is ongoing debate regarding the value of market-based instruments, such as certification schemes, as an approach to improving the environmental impact of fisheries. This article evaluates the effects of the Marine Stewardship Council on the environmental performance of fisheries over the period before and after certification. A large number of fisheries (n = 447) have undertaken pre-assessments, and in most cases (83%), the auditors recommended that significant improvements should be made before entering full assessment. In cases where substantial improvements were required, the proportion of performance indicators scoring over 80 (considered by the Marine Stewardship Council to be the point of best practice) increased by 22% between pre-assessment and certification. Significant improvements continued after certification, characterized by a 16% increase in the proportion of performance indicators scoring over 80 over a period of five years. Increases in scores assigned by auditors were significantly correlated with increases in real environmental performance (such as increases in stock biomass or the development of protected areas) and improvements in information, which led to increasing certainty that impacts were within sustainable limits. Although results show that certification is associated with real environmental benefits, most improvements are made by fisheries that require significant changes to enter the program.