This study investigated biases in the recall of frequency and duration of physical exercise. Following an initial computer-administered self-report interview, 77 subjects maintained diaries for four weeks, in which they recorded the day, time, duration, and type of each exercising bout. Then the interview was administered again, and subjects recalled they exercised more often and for shorter durations than they recorded in their diaries. While social desirability may explain the overestimation of the number of days exercised, the underestimation of exercise duration poses a puzzle. The heuristic of frequency, recency, or prototype could not account for this underestimation. Alternative explanations are explored. Self-reported estimates of exercising duration and frequency should not be taken at face-value until the processes and heuristics used to record and recall exercising behaviors are better understood.