Energy efficiency and the environmental impact of buildings are considered key strategic goals in the EU. However, the resulting increase in energy efficiency of buildings is shifting the environmental burden from the operational to other building life cycle stages. Thus, the presented study investigates the association between the total energy needs and embodied global warming potential (GWP) of building materials on 496,800 building models. These models were parametrically defined through variations of eight different energy-efficiency passive design measures. The results demonstrated that structure material choice significantly determines the total buildings’ embodied GWP. Moreover, decreasing U values below 0.15 W/m2K is questionable as these buildings resulted in a slight reduction of total energy need but a disproportional increase in embodied GWP. Conclusions indicate that passive building energy efficiency measures should be evaluated from both operational and embodied environmental impacts, particularly if the future decarbonization of the energy mix is also considered.