We developed 4 algorithms for syphilis among HIV-positive men who have sex with men who engaged in primary care in 2016 to 2017. Clinician-based diagnosis from chart reviews was the gold standard. Sensitivities ranged from 74.2% to 93.9%. Specificities were greater than 99% with positive and negative predictive values of greater than 95%. Algorithms that incorporated treatment data performed best.