Background: This study aimed to identify unobserved subgroups of persons with similar trajectories of co-occurring behavioral health risk factors (BRFs) over 4 years in an adult general population sample and to examine their relation to education. Methods: Data of 831 control group participants of a randomized controlled trial was analyzed. Participants aged 18–64 years who had consumed alcohol in the past 12 months were recruited at a registry office. Alcohol consumption, tobacco smoking, body mass index, and physical inactivity were assessed at baseline via self-report and 1, 3, and 4 years later. Latent class growth analysis was used to identify BRF trajectories and to test their association with school education, adjusted for sex, age, marital status, and self-rated health. Results: Eight BRF trajectory classes were identified, with the largest class (31% of participants) being characterized by stable low-to-moderate alcohol consumption and an otherwise healthy lifestyle. Higher-educated compared to lower-educated participants were more likely in this class than in other classes, including, among others, a class combining stable alcohol consumption, tobacco smoking, and increasing excess weight (Odds ratio, OR = 7.41, p < 0.001) and a class maintaining absence of BRFs over time (OR = 3.89, p < 0.001). Conclusions: This study demonstrates heterogeneity in BRF trajectories and their relation to education. Although higher-educated persons were more likely in classes with fewer BRFs and favorable BRF changes, alcohol consumption remained a common BRF in several of these trajectories. Trajectories of multiple co-occurring BRFs, particularly those involving tobacco smoking and unfavorable BRF changes, seem to disproportionately affect lower-educated persons.