Purpose: This study aimed to investigate longitudinal associations of objectively measured physical activity (PA) and sedentary behavior (SB) with body composition and physical fitness at a 12-month follow-up in healthy Swedish 4-yr-old children. Methods: The data from the population-based MINISTOP trial were collected between 2014 and 2016, and this study included the 138 children who were in the control group. PA and SB were assessed using the wrist-worn ActiGraph (wGT3x-BT) accelerometer during seven 24-h periods and, subsequently, defined as SB, light-intensity PA, moderate-intensity PA, vigorous-intensity PA (VPA), and moderate-to-vigorous PA (MVPA). Body composition was measured using air-displacement plethysmography and physical fitness (cardiorespiratory fitness, lower and upper muscular strength as well as motor fitness) by the PREFIT fitness battery. Linear regression and isotemporal substitution models were applied. Results: Greater VPA and MVPA at the age of 4.5 yr were associated with higher fat-free mass index (FFMI) at 5.5 yr (P < 0.001 and P = 0.044, respectively). Furthermore, greater VPA and MVPA at the age of 4.5 yr were associated with higher scores for cardiorespiratory fitness, lower body muscular strength, and motor fitness at 12-month follow-up (P = 0.001 to P = 0.031). Substituting 5 min.d(-1) of SB, light-intensity PA, or moderate-intensity PA for VPA at the age of 4.5 yr were associated with higher FFMI, and with greater upper and lower muscular strength at 12-month follow-up (P < 0.001 to P = 0.046). Conclusion: Higher VPA and MVPA at the age of 4.5 yr were significantly associated with higher FFMI and better physical fitness at 12-month follow-up. Our results indicate that promoting high-intensity PA at young ages may have long-term beneficial effects on childhood body composition and physical fitness, in particular muscular strength.