A cycling campaign was assessed that used three different nudging conditions to progress people's stage of motivation to make travel behavioral changes. The results of three waves of survey data showed that this cycling campaign generally strengthened their stage of motivation to reduce car use and that this stage-change, in turn, reduced actual car use while increasing bike use. It was observed that an improvement of cognitive psychological mechanisms was positively related to people's motivation to change. Although the effect of the campaign was stronger just after it had ended (Wave 2), a reduction in car use, an increase in bike use, and an increase in the stage of motivation were still found three months after the campaign had ended. This is important as it shows that effects favoring sustainable travel last beyond the timeframe of the intervention. We conclude that travel interventions should aim to integrate processes that emphasize cognitive psychological mechanisms and people's motivation to change as these drive a sustainable behavioral change.