We investigated the impact of mental fatigue on exploration in a complex computer task. The exploration behavior of participants who underwent a fatigue manipulation (N = 36) was compared with that of a control (nonfatigued) group (N = 32). A distinction was also made between participants with high or low levels of general computer experience. Results showed that fatigued participants used significantly less systematic exploration and made more errors than did nonfatigued participants. Fatigued participants with low computer experience also showed significantly more rigid behavior than did the other participants. No differences were found on the number of subtasks solved. Compared with low-experience participants, highly experienced participants showed significantly more systematic exploration, less unsystematic trial and error, solved more subtasks, and made fewer errors (marginally significant p = .056). Findings were interpreted as the result of reduced task engagement under fatigue and reduced involvement of executive control on behavior. Actual or potential applications of this research include guidelines to prevent detrimental effects of mental fatigue on exploration behavior.