Small food retailers, including corner/convenience stores, pharmacies, gas-marts, and dollar stores, have historically stocked limited fruits and vegetables, though this may be changing. We examined increases in sales, customer purchasing, and stocking of fresh and/or frozen fruits and vegetables in small food stores over time and in relation to: (a) a local food policy (the Minneapolis Staple Foods Ordinance) and (b) neighborhood socioeconomic status (SES). We used longitudinal data (2014–2017) from 147 randomly-sampled stores in Minneapolis/St. Paul, USA, collected using interviewer-administered manager surveys (measuring sales and stocking) and customer intercepts/observations (measuring purchasing, n = 3039). The local policy required Minneapolis stores to meet minimum stocking standards for fresh/frozen produce and other healthy foods. No ordinance existed in St. Paul. Mixed regression models examined overall change over time and change by city and neighborhood SES. We observed significant increases over time (p < 0.05) in sales and purchasing of fresh fruit and in stocking of fresh fruit, frozen fruit, and frozen vegetables. We did not identify consistent statistical evidence for differential change in sales, purchasing, or stocking by city or neighborhood SES. Key study findings suggest limited differential effects of the local ordinance and/or neighborhood SES. However, findings also indicate significant time trends for some products, including consistent improvements in sales, customer purchasing, and stocking of fresh fruit. Given the ready-to-eat convenience of many fresh fruits and their broad appeal, fresh fruit appears a promising target for advancing the healthfulness of small food retailers.