The Native American Health Center provides substance use and mental health services for urban American Indians and Alaska Natives (AIs/ANs) utilizing a culturally based holistic system of care (HSOC). Substance use prevention, treatment, and recovery services emphasize traditional AI/AN healing practices alongside evidence-based practices. This article describes the HSOC approach and provides preliminary findings from an outcome evaluation. Participants in outpatient and residential treatment were interviewed at baseline and 6-month follow-up with a standardized assessment tool (n = 490). The sample we composed of 86% AI/AN, 70% females, 30% males, and was entirely urban. Decreases in substance use and its related consequences were evident in both modalities but were most pronounced in residential treatment. Study's limitations and implications are included.