This paper contributes to the debate on early-career precariousness and inequalities against the backdrop of labour market deregulation. The analyses focus on a cohort of young Italian workers who entered the labour market after the deregulatory reforms of the late 1990s and early 2000s. Instead of looking at the timing of isolated transitions between employment states, 7-year-long trajectories are considered to identify differences by gender and education in the probability of experiencing more stable and protected early-careers. Italy is a particularly interesting country-case because of its high youth unemployment rates and difficult school-to-work transitions into the protected labour market segment. The analyses draw on AD-SILC, a unique data source that combines administrative records of complete employment histories and survey data and offers an unprecedented, highly detailed distinction between a wide range of non-standard employment relationships. Applying sequence analysis, eight early-career types characterized by different degrees of employment continuity and stability are identified. Multivariate logistic regression estimates show that women—especially if lower-educated—are more likely than men to experience pathways characterized by instability and weak (or absent) employment and social security protection, that ultimately lead to more precarious early careers.