We show that US natural gas prices have decoupled from oil prices following substantial institutional and technological changes. We then examine how this interrelationship has evolved in Europe using data for Algeria, one of Europe's key gas suppliers. Taking into account total gas exports and cyclical conditions in partner countries, we find that gas prices remain linked to oil prices, though the nexus has loosened. Both high oil prices and a modest industrial recovery in partner countries have kept gas exports at low levels in recent years, suggesting changing market forces. The paper then shows how such shifts can have important macroeconomic implications for a big gas exporter such as Algeria.