Physical activity has been shown to benefit brain and cognition in late adulthood. However, this effect is still unexplored in terms of brain signal complexity, which reflects the level of neural adaptability and efficiency during cognitive processing that cannot be acquired via averaged neuroelectric signals. Here we employed multiscale entropy analysis (MSE) of electroencephalography (EEG), a new approach that conveys important information related to the temporal dynamics of brain signal complexity across multiple time scales, to reveal the association of physical activity with neural adaptability and efficiency in elderly adults. A between-subjects design that included 24 participants (aged 66.63. ±. 1.31. years; female. = 12) with high physical activity and 24 age- and gender-matched low physical activity participants (aged 67.29. ±. 1.20. years) was conducted to examine differences related to physical activity in performance and MSE of EEG signals during a visuo-spatial cognition task. We observed that physically active elderly adults had better accuracy on both visuo-spatial attention and working memory conditions relative to their sedentary counterparts. Additionally, these physically active elderly adults displayed greater MSE values at larger time scales at the Fz electrode in both attention and memory conditions. The results suggest that physical activity may be beneficial for adaptability of brain systems in tasks involving visuo-spatial information. MSE thus might be a promising approach to test the effects of the benefits of exercise on cognition.