Background: Atrial fibrillation (AF) affects more than 2 million Americans and results in a five-fold increased rate of embolic strokes if left untreated. Although the efficacy of adjusted-dose warfarin in reducing this risk for ischemic stroke by 68% is well documented, many patients are not receiving treatment consistent with guidelines. The use of a patient-specific computerized decision support tool may aid in closing the knowledge gap regarding the best treatment for a patient. Methods: This retrospective, observational cohort analysis of 6,123 Ohio Medicaid patients used a patient-specific computerized decision support tool that automated the complex risk-benefit analysis of anticoagulation. Patient-specific factors were ascertained from the twelve months of claim information prior to incident atrial fibrillation diagnosis. Adverse outcomes of acute stroke, major gastrointestinal bleeding, intracranial hemorrhage, and other bleeding were determined from Ohio Medicaid inpatient claims and Ohio death registry information. Cox proportional hazards models were developed to compare the group of patients who received warfarin treatment to those who did not receive warfarin treatment, stratified by the anticoagulation recommendation from the decision-support tool. Results: The decision support tool recommended warfarin for 3,008 patients (49%); however, only 9.9% of these were prescribed warfarin. In patients for whom anticoagulation was recommended by the decision support tool, there was a trend towards a decreased hazard for stroke with actual warfarin treatment (hazard ratio of 0.90) without significant increase in gastrointestinal hemorrhage (hazard ratio of 0.87). In contrast, in patients for whom the tool recommended no anticoagulation, there was a statistically significant increased hazard of gastrointestinal bleeding (hazard ratio of 1.54), although those treated with warfarin still demonstrated a trend toward decreasing hazard of stroke. Conclusions: We have shown that our atrial fibrillation decision-support tool is a useful predictor of those at risk of major bleeding for whom anticoagulation may not necessarily be beneficial, based on analysis of the Ohio Medicaid population. While the decision support tool does not include patient-specific preferences or physician barriers to warfarin use, it nevertheless confirms that many of these patients (49%) should be considered for anticoagulation. Thus, a decision support tool may aid in weighing the benefits versus risks of anticoagulation treatment for patients with nonvalvular atrial fibrillation.