Languages are tools to narrate about the past, capture the here and now, and construct the future. They externalize the human mind, help distribute ideas, and take the burden off the memory of individuals. To fulfil their purpose, a certain level of complexity is needed. How much complexity is enough? More precisely, how can complexity be measured and compared across diverse languages? How and why does complexity change over historical time? Are all languages ultimately equally complex? And finally, when in the hominin lineage did languages reach the complexity levels of today? Despite several decades of research, no consensus has been reached on these controversial questions. This talk provides conceptual and methodological impetus to investigate language complexity in shallow and deep time.