This work investigates the relation between the complexity of electroencephalography (EEG) signal, as measured by fractal dimension (FD), and normal sleep structure in terms of its macrostructure and microstructure. Sleep features are defined, encoding sleep stage and cyclic alternating pattern (CAP) related information, both in short and long term. The relevance of each sleep feature to the EEG FD is investigated, and the most informative ones are depicted. In order to quantitatively assess the relation between sleep characteristics and EEG dynamics, a modeling approach is proposed which employs subsets of the sleep macrostructure and microstructure features as input variables and predicts EEG FD based on these features of sleep micro/macrostructure. Different sleep feature sets are investigated along with linear and nonlinear models. Findings suggest that the EEG FD time series is best predicted by a nonlinear support vector machine (SVM) model, employing both sleep stage/transitions and CAP features at different time scales depending on the EEG activation subtype. This combination of features suggests that short-term and long-term history of macro and micro sleep events interact in a complex manner toward generating the dynamics of sleep.