Assessing evolution of cognitive structures across historical periods has remained challenging in the absence of direct access to humans from the past. Overcoming some of these challenges, we examined shifts in the implicit cognitive structures in the Epic of Gilgamesh, which is one of the earliest surviving pieces of literature, circulating in various versions over a period of approx. 2000 years in ancient Mesopotamia. Using a canonical English translation, we applied natural language processing (NLP) and human coding to extract low-dimensional representations of the implicit personality structure in three different historical epochs. We found systematic shifts over time with increasing complexity and increasing resemblance of contemporary personality models in later periods. We discuss how lexical analyses of ancient texts using trait co-occurrence analyses can provide novel insights on the evolution of human behaviour of relevance for contemporary social and behavioural science and the study of ancient societies.