Background: Several health organizations have adopted the 5A's brief intervention model (Ask, Advise, Assess, Assist, Arrange), based on evidence-based guidelines for smoking cessation. We examine individual, cognitive, behavioral, and organizational factors associated with the 5A's performance among clinical healthcare workers in Catalonia. We also investigate how these factors interact and potentially predict the implementation of each component of the 5A's. Methods: A cross-sectional survey was conducted among clinical health workers enrolled in an online smoking cessation training course (n = 580). The survey included questions about individual characteristics as well as cognitive, behavioral, and organizational factors previously identified in research. We assessed self-reported performance of the 5A's, assessed on a scale from 0 to 10, and used Multivariate regression to examine factors associated with its performance. Results: The performance means (standard deviation) were moderate for the first 3A's [Ask: 6.4 (3.1); Advise: 7.1 (2.7); Assess: 6.3 (2.8)] and low for the last 2A's [Assist: 4.4 (2.9); Arrange: 3.2 (3.3)]. We observed a high correlation between Assist and Arrange (r = 0.704, p < 0.001). Having positive experiences and feeling competent were positively associated with performing the 5A's model and having organizational support with Assist and Arrange. Personal tobacco use among healthcare workers was negatively associated with Advice and Arrange. Conclusions: Our study found that clinical healthcare workers do not perform the 5A's completely. The main barriers identified suggest the need of training and making available practical guidelines in healthcare services. Organizational support is essential for moving towards the implementation of Assist and Arrange.