Background. Threshold analysis is used to determine the threshold value of an input parameter at which a health care strategy becomes cost-effective. Typically, it is performed in a deterministic manner, in which inputs are varied one at a time while the remaining inputs are each fixed at their mean value. This approach will result in incorrect threshold values if the cost-effectiveness model is nonlinear or if inputs are correlated. Objective. To propose a probabilistic method for performing threshold analysis, which accounts for the joint uncertainty in all input parameters and makes no assumption about the linearity of the cost-effectiveness model. Methods. Three methods are compared: 1) deterministic threshold analysis (DTA); 2) a 2-level Monte Carlo approach, which is considered the gold standard; and 3) a regression-based method using a generalized additive model (GAM), which identifies threshold values directly from a probabilistic sensitivity analysis sample. Results. We applied the 3 methods to estimate the minimum probability of hospitalization for typhoid fever at which 3 different vaccination strategies become cost-effective in Uganda. The threshold probability of hospitalization at which routine vaccination at 9 months with catchup campaign to 5 years becomes cost-effective is estimated to be 0.060 and 0.061 (95% confidence interval [CI], 0.058–0.064), respectively, for 2-level and GAM. According to DTA, routine vaccination at 9 months with catchup campaign to 5 years would never become cost-effective. The threshold probability at which routine vaccination at 9 months with catchup campaign to 15 years becomes cost-effective is estimated to be 0.092 (DTA), 0.074 (2-level), and 0.072 (95% CI, 0.069–0.075) (GAM). GAM is 430 times faster than the 2-level approach. Conclusions. When the cost-effectiveness model is nonlinear, GAM provides similar threshold values to the 2-level Monte Carlo approach and is computationally more efficient. DTA provides incorrect results and should not be used.