Background There is increasing awareness of the need to analyse symptoms of mental ill-health among early school leavers. Dropping out of compulsory education limits access to the labour market and education and could be related to deteriorating mental health over the course of a lifetime. The aim of this longitudinal study is to explore how early school leavers not in education, employment or training (NEET) narrate their working life trajectories linked to health, agency and gender relations. Methods Twelve early school leavers in the Swedish Northern Cohort (six women and six men) were interviewed over 40 years about their working life and health. Their life stories were analysed using structural narrative analysis to examine the evolution of their working life paths and to identify commonalities, variations and gendered patterns. Results All the participants started in the same position of “an unhealthy gendered working life in youth due to NEET status”. Subsequently, three distinct working life paths evolved: “a precarious gendered working life with negative health implications”, “a stable gendered working life in health challenging jobs” and “a self-realising gendered working life with improved health”. Agency was negotiated through struggle narratives, survival narratives, coping narratives and redemption narratives. Conclusions Even in a welfare regime like Sweden’s in the early 1980s, early school leavers not in education, employment or training experienced class-related and gendered working and living conditions, which created unequal conditions for health. Despite Sweden’s active labour market policies and their own practices of agency, the participants still ended up NEET and with precarious working life paths. Labour market policies should prioritise reducing unemployment, combating precarious employment, creating job opportunities, providing training and subsidised employment in healthy environments, and offering grants to re-enter further education. Our study highlights the need for further analyses of the contextual and gendered expressions of health among early school leavers throughout their lifetime, and of individual agency in various contexts for overcoming adversities.