Catchment water quality models have many parameters, several output variables and a complex structure leading to multiple minima in the objective function. General uncertainty/optimization methods based on random sampling (e.g. GLUE) or local methods (e.g. PEST) are often not applicable for theoretical or practical reasons. This paper presents “ParaSol”, a method that performs optimization and uncertainty analysis for complex models such as distributed water quality models. Optimization is done by adapting the Shuffled Complex Evolution algorithm (SCE-UA) to account for multi-objective problems and for large numbers of parameters. The simulations performed by the SCE-UA are used further for uncertainty analysis and thereby focus the uncertainty analysis on solutions near the optimum/optima. Two methods have been developed that select “good” results out of these simulations based on an objective threshold. The first method is based on χ2 statistics to delineate the confidence regions around the optimum/optima and the second method uses Bayesian statistics to define high probability regions. The ParaSol method was applied to a simple bucket model and to a Soil and Water Assessment Tool (SWAT) model of Honey Creek, OH, USA. The bucket model case showed the success of the method in finding the minimum and the applicability of the statistics under importance sampling. Both cases showed that the confidence regions are very small when the χ2 statistics are used and even smaller when using the Bayesian statistics. By comparing the ParaSol uncertainty results to those derived from 500,000 Monte Carlo simulations it was shown that the SCE-UA sampling used for ParaSol was more effective and efficient, as none of the Monte Carlo samples were close to the minimum or even within the confidence region defined by ParaSol.