Background: In the fight against rising overweight and obesity levels, and unhealthy urban environments, the renaissance of active mobility (cycling and walking as a transport mode) is encouraging. Transport mode has been shown to be associated to body mass index (BMI), yet there is limited longitudinal evidence demonstrating causality. We aimed to associate transport mode and BMI cross-sectionally, but also prospectively in the first ever European-wide longitudinal study on transport and health. Methods: Data were from the PASTA project that recruited adults in seven European cities (Antwerp, Barcelona, London, Oerebro, Rome, Vienna, Zurich) to complete a series of questionnaires on travel behavior, physical activity levels, and BMI. To assess the association between transport mode and BMI as well as change in BMI we performed crude and adjusted linear mixed-effects modeling for cross-sectional (n = 7380) and longitudinal (n = 2316) data, respectively. Results: Cross-sectionally, BMI was 0.027 kg/m² (95%CI 0.015 to 0.040) higher per additional day of car use per month. Inversely, BMI was −0.010 kg/m² (95%CI −0.020 to −0.0002) lower per additional day of cycling per month. Changes in BMI were smaller in the longitudinal within-person assessment, however still statistically significant. BMI decreased in occasional (less than once per week) and non-cyclists who increased cycling (−0.303 kg/m², 95%CI −0.530 to −0.077), while frequent (at least once per week) cyclists who stopped cycling increased their BMI (0.417 kg/m², 95%CI 0.033 to 0.802). Conclusions: Our analyses showed that people lower their BMI when starting or increasing cycling, demonstrating the health benefits of active mobility.