High prevalence of obesity and non-communicable diseases is a global public health problem, in which the quality of food environments is thought to play an important role. Current scientific evidence is not consistent regarding the impact of food environments on diet. The relationship between local food environments and diet quality was assessed across 10 Australian suburbs, using Australian-based indices devised to measure the two parameters. Data of dietary habits from the participants was gathered using a short questionnaire. The suburbs’ Food Environment Score (higher being healthier) was associated with higher consumption of fruit (χ2 (40, 230) = 58.8, p = 0.04), and vegetables (χ2 (40, 230) = 81.3, p = 0.03). The Food Environment Score identified a significant positive correlation with four of the diet scores: individual total diet score (rs = 0.30, p < 0.01), fruit and vegetable score (rs = 0.43, p < 0.01), sugary drink score (rs = 0.13, p < 0.05), and discretionary food score (rs = 0.15, p < 0.05). Moreover, the suburbs’ RFEI (Retail Food Environment Index, higher being unhealthier) showed a significant association with higher consumption of salty snacks (χ2 (24, 230) = 43.9, p = 0.04). Food environments dominated by food outlets considered as ‘healthier’ were associated with healthier population food intakes, as indicated by a higher consumption of fruit, vegetables, and water, as well as a lower consumption of junk food, salty snacks, and sugary drinks. This association suggests that healthier diet quality is associated with healthier food environments in regional Australia.