The Lidcombe Program is an operant treatment for early stuttering. Outcomes indicate that the program is effective; however, the underlying mechanisms leading to a successful reduction of stuttering remain unknown. The purpose of this study was to determine whether fluency achieved with the Lidcombe Program was accompanied by concomitant reduction of utterance length and decreases in linguistic complexity. Standardized language tests were administered pretreatment to 4 male preschool children. Spontaneous language samples were taken 2 weeks prior to treatment, at Weeks 1, 4, 8, and 12 during treatment, and 6 months after the onset of treatment. Samples were analyzed for mean length of utterance (MLU), percentage of simple and complex sentences, number of different words (NDW), and percentage of syllables stuttered. Analysis revealed that all participants presented with language skills in the average and above average range. The children achieved an increase in stutter-free speech accompanied by increases in MLU, percentage of complex sentences, and NDW. For these preschool children who stutter, improved stutter-free speech during treatment with the program appeared to be achieved without a decrease in linguistic complexity. Theoretical and clinical implications are discussed.