Fatigued driving is one of the major causes of traffic accidents. Frequent repetition of driving behavior for a long time may lead to driver fatigue, which is closely related to the central nervous system. In the present work, we designed a fatigue driving simulation experiment and collected the electroencephalogram (EEG) signals. Complex network theory was introduced to study the evolution of brain dynamics under different rhythms of EEG signals during several periods of the simulated driving. The results show that as the fatigue degree deepened, the functional connectivity and the clustering coefficients increased while the average shortest path length decreased for the delta rhythm. In addition, there was a significant increase of the degree centrality in partial channels on the right side of the brain for the delta rhythm. Therefore, it can be concluded that driving fatigue can cause brain complex network characteristics to change significantly for certain brain regions and certain rhythms. This exploration may provide a theoretical basis for further finding objective and effective indicators to evaluate the degree of driving fatigue and to help avoid fatigue driving.