Although natural languages are generally arbitrary in their mapping of forms to meanings, there are some biases. For example, longer words tend to refer to meanings that are more conceptually complex (a complexity bias; Lewis, Sugarman, & Frank, 2014). The origins of this bias remain an open question, however. One hypothesis is that this regularity is the product of a complexity bias in individual speakers, and that it emerges in the lexicon over the course of language evolution. In the present work, we use an iterated learning paradigm to explore this proposal. Speakers learned labels of varying lengths for objects of varying complexity, and then were asked to recall the labels. We then presented the labels that participants produced to a new set of speakers, iterating this procedure across generations. The results suggest a complexity bias that guides language change but that interacts with pressures for simplicity.