COVID-19 has disrupted food access and impacted food insecurity, which is associated with numerous adverse individual and public health outcomes. To assess these challenges and understand their impact on food security, we conducted a statewide population-level survey using a convenience sample in Vermont from 29 March to 12 April 2020, during the beginning of a statewide stay-at-home order. We utilized the United States Department of Agriculture six-item validated food security module to measure food insecurity before COVID-19 and since COVID-19. We assessed food insecurity prevalence and reported food access challenges, coping strategies, and perceived helpful interventions among food secure, consistently food insecure (pre-and post-COVID-19), and newly food insecure (post COVID-19) respondents. Among 3219 respondents, there was nearly a one-third increase (32.3%) in household food insecurity since COVID-19 (p < 0.001), with 35.5% of food insecure households classified as newly food insecure. Respondents experiencing a job loss were at higher odds of experiencing food insecurity (OR 3.06; 95% CI, 2.114–0.46). We report multiple physical and economic barriers, as well as concerns related to food access during COVID-19. Respondents experiencing household food insecurity had higher odds of facing access challenges and utilizing coping strategies, including two-thirds of households eating less since COVID-19 (p < 0.001). Significant differences in coping strategies were documented between respondents in newly food insecure vs. consistently insecure households. These findings have important potential impacts on individual health, including mental health and malnutrition, as well as on future healthcare costs. We suggest proactive strategies to address food insecurity during this crisis.