This paper examines how enhanced flexibility across space, time, and a regulatory dimension affects the economic costs and CO2 emissions of integrating large shares of intermittent renewable energy from wind and solar. We develop a numerical model which resolves hourly dispatch and investment choices among heterogeneous energy technologies and natural resources in interconnected wholesale electricity markets, cross-country trade (spatial flexibility), energy storage (temporal flexibility), and tradable green quotas (regulatory flexibility). Taking the model to the data for the case of Europe's system of interconnected electricity markets, we find that the appropriate combination of flexibility can bring about substantial gains in economic efficiency, reduce costs (up to 13.8%) and lower CO$_2$ emissions (up to 51.2%). Regulatory flexibility is necessary to realize most of the maximum possible benefits. We also find that gains from increased flexibility are unevenly distributed and that some countries incur welfare losses.