We used a discrete-event simulation model of the natural history of Colorectal Cancer (CRC) to do a cost-effectiveness analysis comparing the latest CRC screening strategies recommended by the American Gastroenterological Association (AGA) and the newest screening modalities for which clinical efficacy has been established. Cost-effectiveness was based on discounted costs and quality-adjusted life-years. A probabilistic sensitivity analysis examined the uncertainty in important parameter estimates. Considering all populations (average and high risk), annual Fecal Occult Blood Test (FOBT), Sigmoidoscopy every five years and annual FOBT, and Colonoscopy every ten years were the three strategies that demonstrated a greater than 50% probability of not being dominated in probabilistic sensitivity analysis. Depending on the maximum acceptable marginal cost-effectiveness value, any of these procedures have a high likelihood of becoming preferred (most effective strategy given a specific cost limit per Quality-Adjusted Life-Year (QALY) saved).