Alcohol and tobacco use may lead to negative treatment outcomes in tuberculosis (TB) patients, and even more so if they are HIV-infected. We developed and tested the feasibility of a complex behavioral intervention (ProLife) delivered by lay health workers (LHWs) to improve treatment outcomes in TB patients who smoke tobacco and/or drink alcohol, at nine clinics in South Africa. The intervention comprised three brief motivational interviewing (MI) sessions augmented with a short message service (SMS) program, targeting as appropriate: tobacco smoking, harmful or hazardous drinking and medication adherence. Patients received SMSs twice a week. We measured recruitment and retention rates and assessed fidelity to the MI technique (MI Treatment Integrity 4.1 tool). Finally, we explored LHWs' and patients' experiences through interviews and semi-structured questionnaires, respectively. We screened 137 TB patients and identified 14 smokers, 13 alcohol drinkers, and 18 patients with both behaviors. Participants' mean age was 39.8 years, and 82.2% were men. The fidelity assessments pointed to the LHWs' successful application of key MI skills, but failure to reach MI competency thresholds. Nevertheless, most patients rated the MI sessions as helpful, ascribed positive attributes to their counselors, and reported behavioral changes. SMSs were perceived as reinforcing but difficult language and technical delivery problems were identified as problems. The LHWs' interview responses suggested that they (a) grasped the basic MI spirit but failed to understand specific MI techniques due to insufficient training practice; (b) perceived ProLife as having benefitted the patients (as well as themselves); (c) viewed the SMSs favorably; but (d) considered limited space and privacy at the clinics as key challenges. The ProLife program targeting multiple risk behaviors in TB patients is acceptable but LHW training protocol, and changes in wording and delivery of SMS are necessary to improve the intervention. Trial registration: ISRCTN62728852.