According to characteristics of the formation of gully network due to overtopping, we establish a cellular automata model to simulate the gully network formation. In the model of cellular automata, the water movement is sloping, and the rules of runoff and erosion of slope surface are determined by simulating slope surface erosion in association with the scour rate formula. Random topographic fluctuation and differences in anti-scouring performance of slope surface are taken into account in the calculation. Results indicate that the gully network is straight if only the random topographic fluctuation is considered, whereas the calculation result by considering the two factors is superior to that by considering single factor.