In recent years, various levels of government in the U.S. have adopted or discussed subsidies, tax breaks, zoning laws, and other public policy instruments to promote geographic access to healthy food. These policies are supposed to reduce obesity. But there is little evidence from large-scale longitudinal or quasi-experimental research suggesting that geographic access to supermarkets, fast food restaurants, and other food outlets actually affect body mass index (BMI). Using a longitudinal design, we examined whether geographic accessibility of food outlets was associated with BMI change between 2009 and 2014 using clinical data for 1.7 million military veterans living in 382 metropolitan areas. We found no evidence that the absolute or relative accessibility of supermarkets, fast food restaurants, or mass merchandisers were associated with individual BMI change. While they may promote equitable access, our findings suggest that policies that alter food outlet accessibility will do little to combat the obesity epidemic.