Biological systems represent time from microseconds to years. An important gap in our knowledge concerns the mechanisms for encoding time intervals of hundreds of milliseconds to minutes that matter for tasks like navigation, communication, storage, recall, and prediction of stimulus patterns. A recently identified mechanism in fish thalamic neurons addresses this gap. Representation of intervals between events uses the ubiquitous property of neural fatigue, where firing adaptation sets in quickly during an event. The recovery from fatigue by the next stimulus is a monotonous function of time elapsed. Here we develop a full theory for the representation of intervals, allowing for recovery time scales and sensitivity to past stimuli to vary across cells. Our Bayesian framework combines parametrically heterogeneous stochastic dynamical modeling with interval priors to predict available timing information independent of actual decoding mechanism. A compromise is found between optimally encoding the latest time interval and previous ones, crucial for spatial navigation. Cellular heterogeneity is actually necessary to represent interval sequences, a novel computational role for experimentally observed heterogeneity. This biophysical adaptation-based timing memory shapes spatiotemporal information for efficient storage and recall in target recurrent networks.