This paper extends our understanding of how the change of a job characteristic over time can influence employee job stress beyond the characteristic per se. In particular, we propose that, with the average level of job complexity during a given period held constant, a job complexity trajectory with greater increment (decrement) is associated with higher (lower) job stress. In addition, based on job-demand-control theory and the personality-stress framework, we theorize that job autonomy and employees’ emotional stability jointly moderate the relationship between job complexity trajectory and employee job stress. Empirical analysis with two sets of longitudinal data provides consistent supports for our hypotheses. We find that (1) for employees with high emotional stability, job autonomy mitigates the positive relationship between job complexity trajectory and job stress, whereas (2) for employees with low emotional stability, job autonomy does not help to reduce the positive effect of job complexity trajectory over time on job stress. Theoretical and practical implications are discussed.