This paper investigates the ecological-economic sustainability of coral reef socio-ecological systems under fishing and environmental pressures. To achieve this, a dynamic, spatially explicit, multi-species, multi-fleet fisheries model is developed. Stochastic environmental shocks are assumed to alter coral cover and consequently the entire coral reef social-ecological system. The model is calibrated using ecological, socio-economic and environmental data in French Polynesia. Four exploratory fishing strategies and a goal-seeking strategy entitled Stochastic Multi-Species Maximum Sustainable Yield (SMMSY) are compared in terms of ecological-economic outcomes and sustainability of the socio-ecological system. The SMMSY turns out to promote ecological-economic sustainability. It is characterised by a global increase in fishing effort pointing to the relative current under-exploitation of the fishery. SMMSY balances the trophic level of catches after natural shocks and sustains the fundamental herbivore grazing process. SMMSY strategies are also more diversified in terms of temporality, gears, spatial distribution of fishing and target species.