Tobacco has long held spiritual significance to Native people of North America but, because of recreational use, it has become a health risk relatively recently. More Native people smoke than any other ethnic group (41 percent vs. 24 percent in whites and blacks), and death rates caused by tobacco-related diseases are disproportionately high. However, no tested, culturally tailored smoking cessation programs exist for this group. We used a critical-interpretive framework to understand the meaning of tobacco and the feasibility of smoking cessation interventions in a pan-tribal population. In June 2004, the University of Kansas Medical Center (KUMC) and the Oklahoma Area Indian Health Service (IHS) collaborated on six focus groups with (IHS) patients. The patients served represent over 200 different nations. Our participants provided us with modifications to a currently untested program designed by the Muscogee Nation of Oklahoma's Tobacco Prevention Program to enhance cultural appropriateness, including (1) an emphasis on visual presentation and a "Native" look to program educational materials; (2) comprehensive information about tobacco, quitting, and coping among Native people; (3) an acknowledgment and incorporation of traditional tobacco use and its diversity; and (4) the use of talking circles and counseling with Native facilitators.