Differential access to healthy foods has been hypothesized to contribute to health disparities, but evidence from low and middle-income countries is still scarce. This study examines whether the access of healthy foods varies across store types and neighborhoods of different socioeconomic statuses (SES) in a large Brazilian city. A cross-sectional study was conducted in 2010–2011 across 52 census tracts. Healthy food access was measured by a comprehensive in-store data collection, summarized into two indexes developed for retail food stores (HFSI) and restaurants (HMRI). Descriptive analyses and multilevel models were used to examine associations of store type and neighborhood SES with healthy food access. Fast food restaurants were more likely to be located in low SES neighborhoods whereas supermarkets and full service restaurants were more likely to be found in higher SES neighborhoods. Multilevel analyses showed that both store type and neighborhood SES were independently associated with in-store food measures. We found differences in the availability of healthy food stores and restaurants in Sao Paulo city favoring middle and high SES neighborhoods.