Multilevel societies, containing hierarchically nested social levels, are remarkable social structures whose origins are unclear. The social relationships of sperm whales are organized in a multilevel society with an upper level composed of clans of individuals communicating using similar patterns of clicks (codas). Using agent-based models informed by an 18-year empirical study, we show that clans are unlikely products of stochastic processes (genetic or cultural drift) but likely originate from cultural transmission via biased social learning of codas. Distinct clusters of individuals with similar acoustic repertoires, mirroring the empirical clans, emerge when whales learn preferentially the most common codas (conformism) from behaviourally similar individuals (homophily). Cultural transmission seems key in the partitioning of sperm whales into sympatric clans. These findings suggest that processes similar to those that generate complex human cultures could not only be at play in non-human societies but also create multilevel social structures in the wild.