An estimated 22% of Americans currently use smokeless tobacco (ST). Most live in small towns and rural areas that offer few ST cessation resources. Approximately 94 million Americans use the Internet for health-related information, and on-line access is growing among lower-income and less-educated groups. As part of a randomized clinical trial to assess the reach and effectiveness of Web-based programs for delivering an ST cessation intervention, the authors developed and evaluated several methods for overcoming the recruitment challenges associated with Web-based research. This report describes and evaluates these methods. Participants were recruited through: (a) Thematic promotional “releases” to print and broadcast media, (b) Google ads, (c) placement of a link on other Web sites, (d) limited purchase of paid advertising, (e) direct mailings to ST users, and (f) targeted mailings to health care and tobacco control professionals. Combined recruitment activities resulted in more than 23,500 hits on our recruitment website from distinct IP addresses over 15 months, which yielded 2,523 eligible ST users who completed the registration process and enrolled in the study. Self-reports revealed that at least 1,276 (50.6%) of these participants were recruited via mailings, 874 (34.6%) from Google ads or via search engines or links on another Web site, and 373 (14.8%) from all other methods combined. The use of thematic mailings is novel in research settings. Recruitment of study participants went quickly and smoothly. Google ads and mailings to media outlets were the methods that recruited the highest number of participants.