Work complexity can be an important factor contributing to the observed employment and wage developments. Using German data, we find that it increased substantially between 1986 and 2012. Work complexity was higher for high-educated employees in the past but differences have leveled out in 2012 due to a steeper increase in complexity among lower educated. Although complexity is associated with higher wages, expected returns have decreased substantially since 1986. Lower education was associated with higher returns to complexity but these decreased over time, too. Thus, the more complexity becomes "normal", the less it is important in determining the wage.