Tobacco smoking among those seeking treatment for cannabis use disorder (CUD) is common and is a negative predictor of cannabis outcomes. Quitting tobacco may be beneficial for those seeking to quit cannabis use. This initial proof of concept, controlled trial was designed to compare a simultaneous versus sequential tobacco intervention among those seeking treatment for CUD. Sixty-seven adults received either a simultaneous (SIM) or sequential (SEQ) approach to tobacco cessation in the context of outpatient treatment for CUD. A tobacco intervention (TI) that combined web-based counseling with nicotine replacement therapy (NRT) was provided during weeks 1-12 for SIM and was delayed until weeks 13-24 for SEQ. During weeks 1-12, no between-condition significant differences were observed on treatment participation or cannabis use outcomes. The majority of SIM participants initiated TI counseling (62%), 50% made at least one quit attempt and 41% initiated NRT. Interestingly, 39% in SEQ made tobacco quit attempts and 18% initiated NRT on their own before the TI was offered to them. However, only 30% of those in SEQ continued treatment during weeks 13-24, which compromised between-condition comparisons following the TI, but illustrated a potential clinical concern with delaying the TI. Tobacco cessation outcomes generally were poor and did not differ between conditions. This initial controlled trial suggests that addressing tobacco use during CUD treatment is acceptable and generates action towards tobacco cessation. Additional trials testing more intensive TI models may be necessary to identify more efficacious interventions for co-use of cannabis and tobacco.