Supporting the implementation of school food and nutrition policies is an international priority to encourage healthier eating among children and youth. Schools are an important intervention setting to promote childhood nutrition, and many jurisdictions have adopted policies, guidelines, and programs to modify the school nutrition environment and promote healthier eating. The purpose of this study was to explore the association between perceived adequacy of facilities or equipment and capacity of staff to support policy implementation with food availability and policy adherence in the province of Nova Scotia (NS), Canada, one of the first regions in Canada to launch a comprehensive school food and nutrition policy (SFNP). A cross-sectional online survey was conducted in 2014-2015 to provide a current-state assessment of policy implementation and adherence. Adequacy and capacity for food policy implementation was used to assess policy adherence through the availability of prohibited 'minimum' nutrition foods. An exploratory factor analysis was conducted on a selection of available foods, and 'slow'- and 'quick'-service food composition measures were dichotomized for food availability. Schools with above-average perceived adequacy and capacity for policy implementation had greater odds (OR = 3.62, CI = 1.56, 8.40) of adhering to a lunch policy, while schools that adhered to a snack and lunch policy had lower odds (OR = 0.48, CI = 0.23, 1.01 and OR = 0.18, CI = 0.08, 0.41) of serving quick-service foods. This study identified the need for appropriate adequacy of facilities or equipment and capacity of staff for policy implementation to ensure policy adherence and improve the school food environment. These findings highlight the relationship between school food and nutrition policies, suggesting that better supporting their implementation could increase the likelihood of their success.