Background: Smoking now represents one of the biggest modifiable risk factors for disease and mortality in people living with HIV (PLHIV). To produce significant changes in smoking rates among this population, treatments will need to be both acceptable to the larger segment of PLHIV smokers and feasible to implement in busy HIV clinics. The purpose of this study was to evaluate the feasibility and effects of a novel proactive algorithm-based intervention in an HIV/AIDS clinic. Methods: PLHIV smokers (N = 100) were proactively identified through their electronic medical records and were subsequently randomized at baseline to receive a 12-week pharmacotherapy-based algorithm treatment or treatment as usual. Participants were tracked in-person for 12 weeks. Participants provided information on smoking behaviors and associated constructs of cessation at each follow-up session. Results: The findings revealed that many smokers reported using prescribed medications when provided with a supply of cessation medication as determined by an algorithm. Compared with smokers receiving treatment as usual, PLHIV smokers prescribed these medications reported more quit attempts and greater reduction in smoking. Proxy measures of cessation readiness (eg, motivation, self-efficacy) also favored participants receiving algorithm treatment. Conclusions: This algorithm-derived treatment produced positive changes across a number of important clinical markers associated with smoking cessation. Given these promising findings coupled with the brief nature of this treatment, the overall pattern of results suggests strong potential for dissemination into clinical settings and significant promise for further advancing clinical health outcomes in this population.