The local food environment plays an important role in the health of adolescents, especially in rural areas. Often, rural areas lack the accessibility and availability of healthy food choices, making a healthy lifestyle difficult to achieve. This study presents a cross-sectional survey of rural adolescents in 8 counties in Kentucky and North Carolina to determine the association between food store choice, body mass index (BMI), and key dietary outcomes. Although BMI had no association with food store choice, those who infrequently shopped at gas stations, convenience stores, and fast food restaurants consumed significantly less added sugar (p < 0.05) than those who shopped at those stores more regularly. Increasing the availability and accessibility of food venues with healthy food options such as supermarkets may decrease added sugar intake among rural adolescents.