The change in the grain boundary network during recrystallization and grain growth was studied in a 316L austenitic stainless steel subjected to 5% cold rolling reduction. The primary recrystallization rapidly developed upon heating to 1000 °C, resulting in the development of relatively coarse-grained microstructure with a grain size about 100 μm. The recrystallized microstructures contained large fractions of annealing twins with their ∑3ⁿ SCL boundaries. The latter ones served as interrupters of the ordinary grain boundary network. The fraction of ∑3ⁿ CSL boundaries increased with increasing the grain size during prolonged annealing. On the other hand, the number of interruptions per unit area remained nearly the same during annealing. Hence, the number of interruptions per a grain increased in accordance with a power law function of the grain size with an exponent of 2. The relationships obtained for the grain boundary network evolution can be used to predict the microstructure evolution in austenitic stainless steels during primary recrystallization followed by grain growth.