Human language is unique in its compositional, open-ended, and sequential form, and its evolution is often solely explained by advantages of communication. However, it has proven challenging to identify an evolutionary trajectory from a world without language to a world with language, especially while at the same time explaining why such an advantageous phenomenon has not evolved in other animals. Decoding sequential information is necessary for language, making domain-general sequence representation a tentative basic requirement for the evolution of language and other uniquely human phenomena. Here, using formal evolutionary analyses of the utility of sequence representation we show that sequence representation is exceedingly costly and that current memory systems found in animals may prevent abilities necessary for language to emerge. For sequence representation to evolve, flexibility allowing for ignoring irrelevant information is necessary. Furthermore, an abundance of useful sequential information and extensive learning opportunities are required, two conditions that were likely fulfilled early in human evolution. Our results provide a novel, logically plausible trajectory for the evolution of uniquely human cognition and language, and support the hypothesis that human culture is rooted in sequential representational and processing abilities.