Languages vary considerably in syntactic structure. About 40% of the world'slanguages have subject-verb-object order, and about 40% havesubject-object-verb order. Extensive work has sought to explain this word ordervariation across languages. However, the existing approaches are not able toexplain coherently the frequency distribution and evolution of word order inindividual languages. We propose that variation in word order reflectsdifferent ways of balancing competing pressures of dependency locality andinformation locality, whereby languages favor placing elements together whenthey are syntactically related or contextually informative about each other.Using data from 80 languages in 17 language families and phylogenetic modeling,we demonstrate that languages evolve to balance these pressures, such that wordorder change is accompanied by change in the frequency distribution of thesyntactic structures which speakers communicate to maintain overall efficiency.Variability in word order thus reflects different ways in which languagesresolve these evolutionary pressures. We identify relevant characteristics thatresult from this joint optimization, particularly the frequency with whichsubjects and objects are expressed together for the same verb. Our findingssuggest that syntactic structure and usage across languages co-adapt to supportefficient communication under limited cognitive resources.