Star formation and feedback shape ecosystems within and around galaxies, yet the details on how they affect the interstellar medium (ISM) and shape galactic-scale star formation histories are actively debated. In my talk I use the high resolution (20 pc) VINTERGATAN cosmological zoom-in simulation to study the evolution of the ISM and its star formation efficiency per free-fall time on giant molecular cloud (GMC) scales across cosmic time. The simulated Milky Way-like galaxy experiences periods of starburst activity and short global gas depletion times (1 < z < 5) when the cold ISM reaches its densest and most turbulent states. More quiescent star formation during a secularly evolving phase (z < 1) shows a less dense and turbulent cold ISM with order of magnitude longer global gas depletion times of a few Gyr. Despite significant changes in global star formation timescales, density, and velocity dispersion distributions as a function of redshift, the average star formation efficiency remains at a constant ~1%. This is due to the coupling between the kinetic-to-gravitational energy ratio in star-forming regions with time, consistent with resolved observations of star-forming GMCs (cf. PHANGS). By connecting state-of-the-art simulations with observations, my results can help relieve tensions between turbulence-regulated efficiency models and observational efficiency estimators, improving our understanding of the mechanisms regulating star formation and feedback in galaxies.