BACKGROUND: This study examined the effectiveness of using Physical Activity Consultation (PAC) as an addition to the standard smoking cessation treatment in Malaysia. We explored participants' experiences in terms of physical activity and smoking abstinence with the combined PAC and smoking cessation intervention. METHODS: Walk-in smokers from a local smoking cessation clinic volunteered for the 8-week intervention program, while undergoing standard smoking cessation treatment. In Week 1, a facilitator conducted a face-to-face intervention to explore participants' involvement in physical activity and helped to set physical activity strategies and goals for participants to increase physical activity levels. Participants were provided with follow-up phone calls at Weeks 3 and 6. Participants answered questionnaires that measured smoking withdrawal (Shiffman-Jarvik Withdrawal Scale), cessation self-efficacy (Cessation Self-efficacy Questionnaire), physical activity involvement (International Physical Activity Questionnaire), and mood (Brunel Mood Scale) upon recruitment, at post-intervention and at follow-up 3 months after the intervention ended. Participants also responded to interviews about their experiences with the PAC and smoking cessation treatment at post-intervention and at 3-month follow-up. RESULTS: Seven participants completed the program until follow-up. All were successfully abstinent. Only two participants increased physical activity levels, whereas others maintained their physical activity levels or showed slight decreases. Several themes were identified in this study, including participants' experiences with withdrawal symptoms, smoking cessation self-efficacy, triggers to smoking cessation, thoughts on standard smoking cessation treatment in Malaysia, physical activity involvement, mood, and thoughts and beliefs on combining smoking cessation and physical activity. CONCLUSIONS: This study suggests PAC was helpful in maintaining or increasing the overall physical activity levels of participants and could assist with smoking abstinence. Findings showed that all participants who stayed in the program were successfully abstinent. In general, the findings in this study provided promising results for further research on PAC as an adjunct to smoking cessation treatments in Malaysia. Trial registration This intervention is registered with the Australian New Zealand Clinical Trials Registry (Trial registration number: ACTRN12616000269437).