The EU FP6 UNCOVER project was aimed at producing a rational scientific basis for developing recovery strategies for some ecologically and socio-economically important fish stocks/fisheries in European seas. The immediate objectives were to identify changes experienced during stock depletion/collapses, to understand prospects for recovery, to enhance the scientific understanding of the mechanisms of recovery, and to formulate recommendations on how best to implement long-term management/recovery plans. We extended an earlier analysis conducted within the project of 13 performance criteria in relation to the recovery of more than 30 fish stocks/fisheries worldwide by multivariate exploratory analysis (canonical correspondence analysis), followed by model building [discriminant analysis (DA)] to quantify the relative importance of key performance criteria, singly or combined. Using the existing database, DA indicated that the four best additive predictors of successful recovery were “rapid reduction in fishing mortality”, “environmental conditions during the recovery period”, “life-history characteristics” of the target stock, and “management performance criteria”. The model classified the status “recovered” and “non-recovered” assigned originally with nearly 100% accuracy.