Studies that investigate time-based complex prospective memory (PM) functioning in participants with substance use disorders (SUD) in consideration of different PM-phases (planning, retention, initiation, execution) are lacking. This study was designed to investigate performance of young adults with DSM-5 tobacco use disorder (TUD) and healthy controls (HC) in different phases of complex PM. Community participants aged 18–35 (N = 43) completed the modified Six Elements Test that includes the PM-phases planning, retention, initiation, and execution of a time-based complex PM-task (with delay phases and background activities). TUD participants were current daily smokers and fulfilled at least two DSM-5 TUD criteria. TUD did not differ significantly from HC in task planning errors and timely task initiation. No group differences showed in rule adherence and completeness during task conduction (execution). During execution, TUD showed significantly more deviations (Coef. 0.45; p = 0.005) from their originally remembered plans than HC. Young adults with relatively mild TUD do not show general impairments in all phases of short-term, complex, and time-based PM. Future research may investigate whether a greater risk of deviation from originally remembered plans in TUD could play a role in the progression and cessation of smoking behavior.