American Indians have the highest rates of smokeless tobacco (SLT) use of any racial/ethnic group in the United States, yet no proven effective cessation programs exist for them. Because tobacco is a sacred plant to many American Indians, cessation programs must not portray it in a completely negative manner. Based on our successful All Nations Breath of Life smoking cessation program, we developed and pilot-tested the All Nations Snuff Out Smokeless (ANSOS) program. Of 48 participants who began the program, 33 completed to six months (68.8% retention rate). Among participants who completed the program, 11 (34%) self-reported abstinence. When those lost to follow-up are considered current users, the cessation rate is 22.9%. An additional 14 individuals reported decreasing use (29.2% of all participants), with an average of 3.4 days per week decrease. All Nations Snuff Out Smokeless shows promise as a culturally appropriate SLT cessation program and is ready for efficacy testing.