OBJECTIVES: Large scale simulation models (e.g. Archimedes Model, MISCAN) are increasingly used to predict cost-effectiveness of medical interventions and to drive reimbursement decisions. These models are complex and involve hundreds of parameters and inputs. Quantification of parameter uncertainties using traditional sampling-based approaches (e.g., Monte Carlo sampling and its variants) can be prohibitively expensive for these models. METHODS:  We overcome the limitations of traditional probabilistic sensitivity analysis through a 4-step process. First, we conduct a thorough survey of all parameters and their confidence intervals. Second, we use local sensitivity analysis to evaluate the effects of each parameter on the outcome of interest. Third, based on results from single-parameter sensitivity analysis, we rank and identify a group of parameters that have the largest effects on the outcome. We then employ response surface (RS) approximation methods to create a mathematical model of the model predictions for these parameters. We use Latin Hypercube sampling (LHS) to generate data points and multivariate adaptive regression splines (MARS) to build the response surface approximations. Fourth, we sample parameters from their joint distributions, and then use the constructed response surface to calculate the probability distribution of the predicted outcomes. RESULTS: We apply the above methodology to quantify uncertainties in predictions of the Archimedes Model for effectiveness of colorectal cancer (CRC) screening by colonoscopy (COLO) and fecal immunological test (FIT). We started out with 200 parameters and identified 20 parameters that have significant influences on predicted effectiveness of  CRC screening. We conclude that there is a 89% chance that COLO will save more life years FIT, after accounting for parameter uncertainties. Similarly we estimate that there is a 61% probability that FIT is more cost effective than colonoscopy. CONCLUSIONS: We have developed a robust and efficient methodology for quantifying parameter uncertainties of large-scale simulation models used for cost-effectiveness analysis.