Background: While it is likely that changing food environments have contributed to the rise in obesity rates, very few studies have explored historical trends in the food environment with little, if any, consideration at a nationwide level. This longitudinal, nationwide, and geospatial study aims to examine change over time in proximity to food environments in all urban areas of New Zealand from 2005 to 2015. Method: This study used high quality food outlet data by area-level deprivation within the three largest urban areas of Auckland, Christchurch and Wellington. We hypothesise that distance and travel time by car to supermarkets and fast-food outlets will have decreased over time with the most notable decreases in distance and time occuring in the most deprived areas of urban New Zealand. Change in major chain “fast-food” and “supermarket” outlets as identified by Territorial Authorities between 2005 and 2015 was analysed through the use of multilevel regression models. Results: Findings show a decrease in distance and time to both fast-food outlets and supermarkets. The biggest decrease in distance for supermarkets was seen in the most deprived areas. Conclusion: Our findings contrast and add to previous evidence to demonstrate how changes in the food environment are not uniform, varying by area-level deprivation and by city with more equitable access to supermarkets occurring over time.