Purpose: This study investigated the complexity of stuttering behavior. It described and classified the complexity of stuttering behavior in relation to age, behavioral treatment outcomes, stuttering severity, anxiety-related mental health, impact of stuttering, and gender. Method: For this study, a taxonomy was developed—LBDL-C7—which was based on the Lidcombe Behavioral Data Language of stuttering. It was used by five experienced judges to analyze the complexity of stuttering behavior for 84 adults and adolescents before and after speech restructuring treatment. Data were 3,100 stuttering moments, which were analyzed with nominal logistic regression. Results: The complexity of stuttering behavior appears not to change as a result of treatment, but it does appear to change with advancing age. Complexity of stuttering behavior was found to be independently associated with clinician stuttering severity scores but not with percentage of syllables stuttered or self-reported stuttering severity. Complexity of stuttering behavior was not associated with gender, anxiety, or impact of stuttering. Conclusion: Clinical and research applications of these findings are discussed.