Humans stand out among animals for their unique capacities in domains such as language, culture and imitation, yet it has been difficult to identify cognitive elements that are specifically human. Most research has focused on how information is processed after it is acquired, e.g. in problem solving or 'insight' tasks, but we may also look for species differences in the initial acquisition and coding of information. Here, we show that non-human species have only a limited capacity to discriminate ordered sequences of stimuli. Collating data from 108 experiments on stimulus sequence discrimination (1540 data points from 14 bird and mammal species), we demonstrate pervasive and systematic errors, such as confusing a red-green sequence of lights with green-red and green-green sequences. These errors can persist after thousands of learning trials in tasks that humans learn to near perfection within tens of trials. To elucidate the causes of such poor performance, we formulate and test a mathematical model of non-human sequence discrimination, assuming that animals represent sequences as unstructured collections of memory traces. This representation carries only approximate information about stimulus duration, recency, order and frequency, yet our model predicts non-human performance with a 5.9% mean absolute error across 68 datasets. Because human-level cognition requires more accurate encoding of sequential information than afforded by memory traces, we conclude that improved coding of sequential information is a key cognitive element that may set humans apart from other animals.