In this study, the effect of addition of water-insoluble dietary fiber (IDF) enzymatically extracted from Auricularia auricula on the acidity and viable bacterial count of fermented milk was explored. One-factor-at-a-time method combined with orthogonal array design was used to optimize the formulation (concentrations of IDF, skim milk powder and sodium carboxymethyl cellulose) of fermented milk with added IDF based on sensory evaluation score. The nutrient composition and texture characteristics of the fermented milk prepared using optimized formulation were determined. The results showed that IDF from Auricularia auricula could promote the proliferation of lactic acid bacteria. The optimum formulation consisted of 7% IDF (converted into 0.78% freeze-dried powder) 1.5% sodium carboxymethylcellulose and 2.0% skim milk powder. The prepared fermented milk contained (3.53 ± 0.08)% protein, (3.12 ± 0.03)% fat, (0.78 ± 0.12)% ash, and (19.35 ± 0.49)% solids. Addition of IDF improved the water-holding capacity, hardness, chewiness and viscosity of fermented milk during storage and at the same time showed a protective effect on the starter culture.