Background. Tobacco-related chronic diseases contribute significantly to the increased morbidity and mortality observed in the homeless population. Few homeless service settings address tobacco use among their clients. Method. Directors and staff from emergency and transitional shelters in San Diego County completed a questionnaire on no-smoking policies and smoking cessation services and participated in in-depth, semistructured interviews to examine the barriers to and facilitators of implementing smoke-free policies and cessation services in their facilities. Results. Facilities differed in outdoor restrictions around smoking: 61.5% reported having an outdoor designated smoking zone, and 25% reported having a campus-wide ban on smoking. About one-third of the facilities offered on-site resources for smoking cessation. Although directors and staff supported smoke-free policies, they reported that the increased resources needed to “police” the policy created barriers to implementation. Almost all directors and staff expressed interest in developing an on-site tobacco control program, but they reported that lack of expertise among staff posed challenges to implementing such a program. Conclusion. Our findings suggest that for a tobacco control program to be effective in homeless shelters, it should include training and incentives for staff to implement smoke-free policies and cessation services.