Research into the link between food environments and health is scarce. Research in this field has progressed, and new comprehensive methods (i.e., incorporating all food retail outlets) for classifying food retail environments have been developed and are yet to be examined alongside measures of obesity. In this study, we examine the association and temporal trends between the food environment and BMI of a repeated cross-sectional sample of the adult population between 2008 and 2016. Methods: Food retail data for 264 postal areas of Greater Melbourne was collected for the years 2008, 2012, 2014, and 2016, and a container-based approach was used to estimate accessibility to supermarkets, healthy and unhealthy outlets. Data on BMI for postal areas was obtained from the Victorian Population Health Survey (n = 47,245). We estimated the association between the food environment and BMI using linear mixed models. Results indicated that BMI increased as accessibility to healthy outlets decreased by up to −0.69 kg/m2 (95%CI: −0.95, −0.44). BMI was lower with high and moderate access to supermarkets compared to low access by −0.33 kg/m2 (−0.63, −0.04) and −0.32 kg/m2 (−0.56, −0.07), and with high access to unhealthy outlets compared to low access (−0.38 kg/m2: −0.64, −0.12) and moderate access (−0.54 kg/m2: −0.78, −0.30). Conclusion: Our results show that increasing access and availability to a diverse range of food outlets, particularly healthy food outlets, should be an important consideration for efforts to support good health. This research provides evidence that Australia needs to follow suit with other countries that have adopted policies giving local governments the power to encourage healthier food environments.