Food environments are potential targets for interventions to reduce obesity prevalence, particularly in island settings that are typically dependent on food imports. This observational study aimed to characterise the availability, quality and price of foods and beverages in a nationally representative sample of grocery stores in Malta using the Nutrition Environment Measures Survey for Stores (NEMS-S) instrument, and to examine the association between area-level density of different types of food stores and the likelihood of children living in these areas being overweight or obese. Fieldwork was carried out between March and May 2014. There was a strong positive correlation between store size and NEMS-S score (p = <0.001), suggesting that smaller grocery stores generally offered a smaller range of products and fewer healthy food/beverage options than larger supermarkets. Across all stores, median prices of certain ‘healthier’ versions of foods were more expensive than their less healthy alternatives. A significant association between risk of childhood overweight, and density of confectionery stores in children's locality of residence, was found (OR 1.19; 95% CI: 1.04, 1.37). These baseline findings highlight opportunities to improve the food environment in Malta to support more healthful eating, and may be of particular interest to public health practitioners in island settings.