Mediterranean demersal fisheries are highly multispecific and many of their target stocks are overexploited. In addition, rocketing fuel costs and low market prices of traditionally high-value species are challenging the viability of fisheries. Here, based on the numeric results of a simulation model, we conclude that this situation can be remedied by reducing both fishing mortality and fishing costs. According to our model results, fishing effort reductions of 48–71% would improve the health of fish stocks while increasing the economic profits of Mallorca islands bottom trawl fishery to as much as 1.9 M€ (146% higher than current profits). If all fish stocks were exploited at their MSY (or below) level, the reduction in fishing effort would have to be of 71% from current values. If equilibrium profits from the fishery were to be maximized (MEY), fishing effort would need to be reduced by 48%. These results must be taken with caution due the many sources of uncertainty of our analysis. The modeling tools used to estimate these values are conditional to the adequate treatment of two sources of uncertainty that are particularly problematic in Mediterranean fisheries: insufficiently known recruitment variability and lack of periodic evaluations of the state of many species. Our results show that fishing effort reductions would produce economic yield gains after a period of transition. Further studies on the benefits of changing the size-selection pattern of fisheries, on better estimation of stock–recruitment relationships and on better quantifications of the contribution of secondary species to these fisheries, are expected to improve the scientific recommendations for Mediterranean demersal fisheries toward sustainability principles.