Background: In nonexperimental comparative effectiveness research using health care databases, outcome measurements must be validated to evaluate and potentially adjust for misclassification bias. We aimed to validate claims-based myocardial infarction (MI) algorithms in a Medicaid population using an HIV clinical cohort as the gold standard. Methods: Medicaid administrative data were obtained for the years 2002-2008 and linked to the UNC CFAR HIV Clinical Cohort based on social security number, first name, and last name and MI were adjudicated. Sensitivity, specificity, positive predictive value, and negative predictive value were calculated. Results: There were 1063 individuals included in the study. Over a median observed time of 2.5 years, 17 had an MI. Specificity ranged from 0.979 to 0.993 with the highest specificity obtained using the ICD-9 code 410.xx in the primary or secondary position and a length of stay >3 days. Sensitivity of MI ascertainment varied from 0.588 to 0.824 depending on algorithm. Conclusions: Specificities of varying claims-based MI ascertainment criteria are high but small changes impact positive predictive value in a cohort with low incidence. Sensitivities vary based on ascertainment criteria. Type of algorithm used should be prioritized based on study question and maximization of specific validation parameters that will minimize bias while also considering precision.