Abstract Background Smokers report poorer sleep than nonsmokers and sleep quality deteriorates further during cessation, increasing risk of smoking relapse. Better understanding of the relationship between sleep and relapse-related outcomes could inform novel approaches to smoking cessation support. The aim of this study was to investigate same-day associations of self-reported sleep quality and fatigue severity with factors associated with successful cessation and cessation beliefs, among regular smokers. Methods This cross-sectional observational study (n = 412) collected self-reported sleep quality, fatigue severity, and factors associated with successful cessation and cessation beliefs among regular smokers via an online survey (60% male). Results There was evidence of an association between sleep quality (SQ) and reduced 24-hour (β = −0.12, p = .05) and lifetime (β = −0.09, p = .04) abstinence self-efficacy. In addition, poorer SQ and higher fatigue severity (FS) were associated with increased smoking urges (SQ: β = 0.27, p < .001; FS: β = 0.32, p < .001), increased barriers to cessation (SQ: β = 0.19, p < .001; FS: β = 0.32, p < .001), and increased perceived risks to cessation (SQ: β = 0.18, p < .001; FS: β = 0.26, p < .001). Fatigue severity was weakly associated with increased perceived benefits to cessation (β = 0.12, p = .017). Conclusions Self-reported sleep quality and fatigue severity were associated with multiple factors associated with successful cessation and cessation beliefs. Further research is needed to extend these findings by using different methods to identify the temporal direction of associations and causality. Implications This study is the first to examine associations between sleep quality, fatigue severity, and factors associated with successful cessation and cessation beliefs. Findings show that both sleep quality and fatigue severity are associated with multiple factors associated with successful cessation and could be modifiable targets for future smoking cessation interventions. Furthermore, our data suggest that fatigue severity has an independent effect on multiple factors associated with successful cessation when accounting for sleep quality. This indicates that fatigue, independent of sleep quality, could be an important factor in a quit attempt.