We present an information-theoretical analysis of temporal dependencies in EEG microstate sequences during wakeful rest. We interpret microstate sequences as discrete stochastic processes where each state corresponds to a representative scalp potential topography. Testing low-order Markovianity of these discrete sequences directly, we find that none of the recordings fulfils the Markov property of order 0, 1 or 2. Further analyses show that the microstate transition matrix is non-stationary over time in 80% (window size 10 s), 60% (window size 20 s) and 44% (window size 40 s) of the subjects, and that transition matrices are asymmetric in 14/20 (70%) subjects. To assess temporal dependencies globally, the time-lagged mutual information function (autoinformation function) of each sequence is compared to the first-order Markov model defined by the classical transition matrix approach. The autoinformation function for the Markovian case is derived analytically and numerically. For experimental data, we find non-Markovian behaviour in the range of the main EEG frequency bands where distinct periodicities related to the subject's EEG frequency spectrum appear. In particular, the microstate clustering algorithm induces frequency doubling with respect to the EEG power spectral density while the tail of the autoinformation function asymptotically reaches the first-order Markov confidence interval for time lags above 1000 ms. In summary, our results show that resting state microstate sequences are non-Markovian processes which inherit periodicities from the underlying EEG dynamics. Our results interpolate between two diverging models of microstate dynamics, memoryless Markov models on one side, and long-range correlated models on the other: microstate sequences display more complex temporal dependencies than captured by the transition matrix approach in the range of the main EEG frequency bands, but show finite memory content in the long run.