Abstract Introduction In 2019, smoking prevalence in North Macedonia was one of the world’s highest at around 46% in adults. However, access to smoking cessation treatment is limited and no co-ordinated smoking cessation programmes are provided in primary care. Methods We conducted a three parallel-armed randomised controlled trial (n = 1368) to investigate effectiveness and cost-effectiveness of lung age (LA) or exhaled carbon monoxide (CO) feedback combined with very brief advice (VBA) to prompt smoking cessation compared with VBA alone, delivered by GPs in primary care in North Macedonia. All participants who decided to attempt to quit smoking were advised about accessing smoking cessation medications and were also offered behavioural support as part of the “ACT” component of VBA. Participants were aged ≥ 35 years, smoked ≥ 10 cigarettes per day, were recruited from 31 GP practices regardless of motivation to quit and were randomised (1:1:1) using a sequence generated before the start of recruitment. The primary outcome was biochemically validated 7-day point prevalence abstinence at 4 weeks (wks). Participants and GPs were not blinded to allocation after randomisation, however outcome assessors were blind to treatment allocation. Results There was no evidence of a difference in biochemically confirmed quitting between intervention and control at 4wks (VBA + LA RR 0.90 (97.5%CI: 0.35, 2.27); VBA + CO RR 1.04 (97.5%CI: 0.44, 2.44)), however the absolute number of quitters was small (VBA + LA 1.6%, VBA + CO 1.8%, VBA 1.8%). A similar lack of effect was observed at 12 and 26wks, apart from in the VBA + LA arm where the point estimate was significant but the confidence intervals were very wide. In both treatment arms, a larger proportion reported a reduction in cigarettes smoked per day at 4wks (VBA + LA 1.30 (1.10, 1.54); VBA + CO 1.23 (1.03, 1.49)) compared with VBA. The point estimates indicated a similar direction of effect at 12wks and 26wks, but differences were not statistically significant. Quantitative process measures indicated high fidelity to the intervention delivery protocols, but low uptake of behavioural and pharmacological support. VBA was the dominant intervention in the health economic analyses. Conclusion Overall, there was no evidence that adding LA or CO to VBA increased quit rates. However, a small effect cannot be ruled out as the proportion quitting was low and therefore estimates were imprecise. There was some evidence that participants in the intervention arms were more likely to reduce the amount smoked, at least in the short term. More research is needed to find effective ways to support quitting in settings like North Macedonia where a strong smoking culture persists. Trial registration The trial was registered at http://www.isrctn.com (ISRCTN54228638) on the 07/09/2018.