Algorithms are regularly used to identify persons living with diagnosed human immunodeficiency virus (HIV) (PLWDH) in Medicaid data. To our knowledge, there are no published reports of an HIV algorithm from Medicaid claims codes that have been compared with an HIV surveillance system to assess its sensitivity, specificity, positive predictive value, and negative predictive value in identifying PLWDH. Therefore, our aims in this study were to 1) develop an algorithm that could identify PLWDH in New York State Medicaid data from 2006-2014 and 2) validate this algorithm using the New York State HIV surveillance system. Classification and regression tree analysis identified 16 nodes that we combined to create a case-finding algorithm with 5 criteria. This algorithm identified 86,930 presumed PLWDH, 88.0% of which were verified by matching to the surveillance system. The algorithm yielded a sensitivity of 94.5%, a specificity of 94.4%, a positive predictive value of 88.0%, and a negative predictive value of 97.6%. This validated algorithm has the potential to improve the utility of Medicaid data for assessing health outcomes and programmatic interventions. © The Author(s) 2019. Published by Oxford University Press on behalf of the Johns Hopkins Bloomberg School of Public Health.