The paper explores barriers for designing and implementing policies for the transition to more environmentally sustainable urban mobility, and strategies for overcoming these barriers in three Norwegian cities. Empirical data has been collected by interviewing key informants and analysing relevant documents. The findings show that there is broad political support for placing sustainable mobility high on the political agenda. Challenges appear when policy measures are designed and implemented. Cultural, legal, political, organisational, financial and knowledge-related barriers are identified. Many similar barriers are identified in the three case cities, but differences also appear. The results indicate that the size of the cities as well as the type of policy packages implemented are important factors, impacting both the type and strength of barriers. Several strategies for overcoming barriers have been implemented in the three case cities with success. The implementation of policy packages with a combination of “push” and “pull” measures is perhaps the most important strategy. In addition, using communication strategically and allowing for trials and step-by-step introduction of policy measures are success factors. Better methods for stakeholder involvement and planning tools for bicyclists and pedestrians may increase the acceptance of policy measures and speed up the transition toward sustainable mobility.