The dynamics of the human brain network has attracted broad attention, in recognition of the concept that functional connectivity is not static, but changes its pattern over time, even in the resting state. We hypothesized that analysis of continuously captured time-varying instantaneous phase synchronization between signals from different brain regions might add another dimension to already identified network dynamics. To validate this hypothesis as an aid to elucidating the physiological mechanisms of aging, we examined time-series of instantaneous phase synchronization events in resting-state EEG activity across the brain, in healthy younger and healthy older subjects. We then characterized the temporal dynamics of phase synchronization using multiscale entropy, which quantifies the complexity of brain signal dynamics over multiple time scales. The results of surrogate analyses confirmed that the temporal dynamics of phase synchronization arise from deterministic processes in the neural network system. Group comparison showed region-specific enhanced complexity of temporal dynamics of phase synchronization in older subjects in alpha band predominantly in frontal brain regions, which was not identified by a comparative phase synchronization approach such as phase lag index. Enhanced complexity of temporal dynamics of functional connectivity in older subjects might reflect a general network alteration theory in aging. This is a first report describing the importance of capturing the dynamics of instantaneous phase synchronization and characterizing its temporal organization. Applying this method to neurophysiologic data may provide a novel understanding of dynamical neural network processes in both healthy and pathological conditions.