Visual-spatial attention (VSA) selects relevant sensory information and supports the preparation of responses to this information. Mental rotation (MR) is the ability to rotate an object seen from a certain perspective to a new orientation in space. Exercise stands out as a promising non-pharmacological treatment for cognitive functions. Balance control is known to be related to the visual system. Therefore, the aim was to investigate the effectiveness of video-based balance games and structured balance exercises on VSA and MR with EEG brain oscillations. 30 healthy participants were included in the study. Participants were divided into two groups (structured balance exercises group (SBEG) and video-based balance exercises group (VBBEG)) by randomization. Both groups received exercise sessions 2 days a week for a total of 6 weeks. The mentioned cognitive functions were evaluated by selecting tests previously used in the literature. For the VSA task, after 6 weeks of exercise, occipital theta (4–7 Hz) power decreased in the VBBEG group, while SBEG increased. In the MR task results, high alpha (11–13 Hz) power decreased in VBBEG and increased in SBEG when centroparietal areas were examined. In conclusion, it is thought that the two different exercise methods may affect visual-spatial attention and mental rotation skills in different ways.