The North Sea cod (Gadus morhua, L.) stock has continuously declined over the past four decades linked with overfishing and climate change. Changes in stock structure due to overfishing have made the stock largely dependent on its recruitment success, which greatly relies on environmental conditions. Here we focus on the spatio-temporal variability of cod recruitment in an effort to detect changes during the critical early life stages. Using International Bottom Trawl Survey (IBTS) data from 1974 to 2011, a major spatio-temporal change in the distribution of cod recruits was identified in the late 1990s, characterized by a pronounced decrease in the central and southeastern North Sea stock. Other minor spatial changes were also recorded in the mid-1980s and early 1990s. We tested whether the observed changes in recruits distribution could be related with direct (i.e. temperature) and/or indirect (i.e. changes in the quantity and quality of zooplankton prey) effects of climate variability. The analyses were based on spatially-resolved time series, i.e. sea surface temperature (SST) from the Hadley Center and zooplankton records from the Continuous Plankton Recorder Survey. We showed that spring SST increase was the main driver for the most recent decrease in cod recruitment. The late 1990s were also characterized by relatively low total zooplankton biomass, particularly of energy-rich zooplankton such as the copepod Calanus finmarchicus, which have further contributed to the decline of North Sea cod recruitment. Long-term spatially-resolved observations were used to produce regional distribution models that could further be used to predict the abundance of North Sea cod recruits based on temperature and zooplankton food availability.