Everyday we perform tasks that make us feel fatigued. Theoretical accounts predict that fatigue not only develops due to exertion of effort but also increases how effortful the same action will feel subsequently. However, to date there has been no formalised computational account of subjective perceptions of fatigue and effort, with few studies measuring these sensations directly or quantifying their moment-to-moment changes. In this study, across three experiments, participants were required to exert different levels of physical effort (grip force below maximum capacity) to obtain rewards, rating on each trial how effortful they found exerting force (Experiment 1) or how fatigued they felt (Experiments 2 and 3). Across studies, ratings of fatigue and perception of effort increased over time but also fluctuated on a trial-by-trial basis as a function of both effort exerted and rest. A computational model of fatigue, comprising a recoverable component (with fatigue reducing during rest) and an unrecoverable one (in which it only increases through effort exerted) successfully accounted for subjective responses. It was best able to explain momentary changes in both fatigue and effort perception. This computational model provides insights into the brain mechanisms underpinning the close, dynamic relationship between sensations of fatigue and effort.