Tourism’s contribution to global emissions is significant and is expected to grow as people travel more frequently. The challenges of decarbonization faced by both tourism industry actors and policymakers are considerable. Using a qualitative approach, this study examines how leaders in the Norwegian tourism industry approach carbon mitigation, what they see as the main challenges, and what policy measures they believe are required for efficient decarbonization. Interviews with leaders of large tourism firms in Norway, including aviation, ferries, cruises, and hotel chains, illustrate the complexities of working towards a low-carbon society in a heterogeneous industry. Both sectoral and cross-sectoral policies at international, national, and regional levels are needed to support this transition. Our findings are discussed in relation to the “avoid-shift-improve” model, recognised as essential for achieving sufficient reduction.