This paper presents a new methodology to derive and analyze strategies for a fully decarbonized urban transport system which combines conceptual vehicle design, a large-scale agent-based transport simulation, operational cost analysis, and life cycle assessment for a complete urban region. The holistic approach evaluates technical feasibility, system cost, energy demand, transportation time, and sustainability-related impacts of various decarbonization strategies. In contrast to previous work, the consequences of a transformation to fully decarbonized transport system scenarios are quantified across all traffic segments, considering procurement, operation, and disposal. The methodology can be applied to arbitrary regions and transport systems. Here, the metropolitan region of Berlin is chosen as a demonstration case. The first results are shown for a complete conversion of all traffic segments from conventional propulsion technology to battery electric vehicles. The transition of private individual traffic is analyzed regarding technical feasibility, energy demand and environmental impact. Commercial goods, municipal traffic and public transport are analyzed with respect to system cost and environmental impacts. We can show a feasible transition path for all cases with substantially lower greenhouse gas emissions. Based on current technologies and today’s cost structures our simulation shows a moderate increase in total systems cost of 13–18%.