Labour-market deregulation may have generated more unstable and complex employment life courses. As exposure to highly volatile early-career trajectories has long-lasting consequences for the working lives of individuals, it is especially important to consider how these processes have affected younger workers in countries like Italy. Here, deregulation ‘at the margins’ of the labour market has been characterized by a strong age divide and has exacerbated the separation between insiders and outsiders. We contrast the individualization of risk perspective with the persistent inequality hypothesis by looking at differentials by gender and socio-economic status in the degree of early-career complexity of workers who entered the labour market before and after deregulation. The use of an innovative longitudinal dataset (AD-SILC) which combines administrative records on employment episodes and survey data on individuals’ socio-economic characteristics allows this study to apply advanced methods in sequence analysis to calculate the complexity of seven-year-long early career trajectories. Complexity is measured by considering the number of transitions between employment states and the length of each episode. We find that early-career complexity increased across cohorts, especially for those more exposed to deregulation. Against the scenario of a generalized increase in labour market dualization, this non-linear dynamic especially affected medium and low-educated individuals and was particularly pronounced for women. Although our analytical strategy does not allow for a causal interpretation of mechanisms engendering the observed trends, this empirical evidence is highly relevant for the implication of changes in early career patterns across cohorts for stratification research.