Introduction: Despite substantial interest in the development of health behaviors, there is limited research that has examined the longitudinal relationship between physical activity (PA) and smoking trajectories from youth to adulthood in a Finnish population. This study aimed to identify trajectories of smoking and PA for males and females, and study the relationship between these trajectories from youth to adulthood. Methods: Latent profile analysis (LPA) was used to identify trajectories of smoking and PA separately for males and females among 3355 Finnish adults (52.1% females). Participants’ smoking and PA were assessed five to eight times over a 31-year period (3–18 years old at the baseline, 34–49 years at last follow-up). Multinomial logistic regression analysis was used to study the relationship between the trajectories of smoking and PA. Results: Five smoking trajectories and four to five PA trajectories were identified for males and females. Of the PA trajectory groups, the persistently active group were least likely to follow the trajectories of regular smoking and the inactive and low active groups were least likely to follow non-smoking trajectory group. Likewise, inactive (women only) and low active groups were less likely to belong to the non-smokers group. Conclusions: The study suggests that those who are persistently active or increasingly active have substantially reduced probabilities of being in the highest-risk smoking categories.