We investigate how the mental lexicon changes over the life span using free association data from over 8,000 individuals, ranging from 10 to 84 years of age, with more than 400 cue words per age group. Using network analysis, with words as nodes and edges defined by the strength of shared associations, we find that associative networks evolve in a nonlinear (U-shaped) fashion over the life span. During early life, the network converges and becomes increasingly structured, with reductions in average path length, entropy, clustering coefficient, and small world index. Into late life, the pattern reverses but shows clear differences from early life. The pattern is independent of the increasing number of word types produced per cue across the life span, consistent with a network encoding an increasing number of relations between words as individuals age. Lifetime variability is dominantly driven by associative change in the least well-connected words.