Background A cancer diagnosis can catalyze motivation to quit smoking. Tobacco treatment trials offer cessation resources but have low accrual rates. Digital outreach may improve accrual, but knowledge of how best to recruit smokers with recent diagnoses is limited. Objective This study aims to identify the message frames that were most effective in promoting intent to talk to a physician about participating in a tobacco treatment trial for smokers recently diagnosed with cancer. Methods From February to April 2019, current smokers diagnosed within the past 24 months were recruited from a national web-based panel for a multimethod pilot randomized trial (N=99). Participants were randomized to a 2×3 plus control factorial design that tested 3 unique message frames: proximal versus distal threats of smoking, costs of continued smoking versus benefits of quitting, and gains of participating versus losses of not participating in a tobacco treatment trial. The primary outcome was intent to talk to a physician about participating in a tobacco treatment trial. In phase 1, the main effect within each message factor level was examined using ANOVA and compared with the control condition. Other message evaluation and effectiveness measures were collected and explored in a multivariable model predicting intent to talk to a physician. In phase 2, open-text evaluations of the messages were analyzed using natural language processing software (Leximancer) to generate a thematic concept map and Linguistic Inquiry Word Count to identify and compare the prevalence of linguistic markers among message factors. Results Of the 99 participants, 76 (77%) completed the intervention. Participants who received the cost of continued smoking frame were significantly more likely to intend to talk to their physician about participating in a tobacco treatment trial than those who received the benefits of the quitting frame (mean costs 5.13, SD 1.70 vs mean benefits 4.23, SD 1.86; P=.04). Participants who received the proximal risks of continued smoking frame were significantly more likely to seek more information about participating (mean distal 4.83, SD 1.61 vs mean proximal 5.55, SD 1.15; P=.04), and those who received the losses of not participating frame reported significantly improved perceptions of smoking cessation research (mean gain 3.98, SD 0.83 vs mean loss 4.38, SD 0.78; P=.01). Male participants (P=.006) and those with greater message relevancy (P=.001) were significantly more likely to intend to talk to their physician. Participants’ perceptions of their smoking habits, as well as their motivation to quit smoking, were prevalent themes in the open-text data. Differences in the percentages of affective words across message frames were identified. Conclusions Multimethod approaches are needed to develop evidence-based recruitment messages for patients recently diagnosed with cancer. Future tobacco treatment trials should evaluate the effectiveness of different message frames on smoker enrollment rates. Trial Registration Clinicaltrials.gov NCT05471284; https://clinicaltrials.gov/ct2/show/NCT05471284