Sexual arousal affects cognitive processing, which depends on the coordinated functioning among cortical areas. The aim of this research was to determine whether previous observation of videos with sexual content affects the degree of cortical electroencephalographic (EEG) coupling during performance of an executive task. Cortical EEG correlations were calculated in three groups of heterosexual men under three conditions: at rest; during observation of a video with neutral, aggressive, or erotic content; and while performing the Tower of Hanoi task (TOH). Based on self-reports, it was shown that the erotic video induced general and sexual arousal, while the aggressive video affected valence and general arousal. Task performance was similar in all three groups. During performance of TOH, only the erotic group showed a decreased correlation between prefrontal areas with an increased correlation between parietal and prefrontotemporal areas, specifically in the slow bands. It is likely that these changes in the degree of cortical coupling could be associated with the cognitive strategies or functional adaptations that participants require to adequately solve the task during a state of sexual arousal. These data could contribute to improving our understanding of the central nervous mechanisms that underlie the effect of sexual arousal on the cognitive processes involved in tasks like TOH.