Cognitive–energetical theories of information processing were used to generate predictions regarding the relationship between perceived workload and fatigue within and across consecutive days of work. Repeated measures were taken aboard a naval vessel from a sample of 20 Navy patrol vessel crew members during nonroutine and routine patrols. The hypotheses were tested through growth curve modeling. There was a nonmonotonic relationship between workload and fatigue in the routine patrol; moderate workload was associated with the lowest fatigue. The relationship between workload and fatigue changed over consecutive days in the nonroutine patrol. At the beginning of the patrol, low workload was associated with fatigue. At the end of the patrol, high workload was associated with fatigue. These results suggest that the optimal level of workload can change over time and thus have implications for the management of fatigue, particularly where prolonged operations are involved.