Background: People living with HIV (PLWH) have a high level of interest in quitting smoking, but only a small proportion have sustainable abstinence 6 months after cessation. Few investigations have focused on relapse to smoking among PLWH. In this investigation, we evaluated the prevalence of relapse after smoking cessation and the characteristics associated with smoking relapse using a retrospective, longitudinal cohort of PLWH during an eight-year observation. Methods: All patients aged ≥19 years that reported current smoking during the study period and then reported not smoking on a subsequent tobacco use questionnaire (quitters) were eligible for the study. In addition, patients required at least one subsequent follow-up visit after quitting where smoking status was again reported to allow for assessment of relapse. A Cox proportional hazard model was fit to evaluate factors associated with smoking relapse in PLWH attending routine clinical care. Results: Of the 473 patients who quit smoking in the study, 51% relapsed. In multivariable analysis, factors significantly associated with a higher likelihood of relapse were anxiety symptoms (HR = 1.55, 95% CI [1.11, 2.17]) and at-risk alcohol use (HR = 1.74, 95% CI [1.06, 2.85]), whereas antiretroviral therapy (ART) adherence (HR = 0.65, 95% CI [0.49, 0.99]) and longer time in care (HR = 0.94, 95% CI [0.91, 0.98]) were associated with a reduced likelihood of relapse after cessation. Conclusion: Our study underscores the high prevalence of smoking relapse that exists among PLWH after they quit smoking. Successful engagement in mental health care may enhance efforts to reduce relapse in the underserved populations of PLWH.