The COVID-19 pandemic has exacerbated economic vulnerabilities and disrupted the Australian food supply, with potential implications for food insecurity. This study aims to describe the prevalence and socio-demographic associations of food insecurity in Tasmania, Australia, during the COVID-19 pandemic. A cross-sectional survey (deployed late May to early June 2020) incorporated the U.S. Household Food Security Survey Module: Six-Item Short Form, and fifteen demographic and COVID-related income questions. Survey data (n = 1170) were analyzed using univariate and multivariate binary logistic regression. The prevalence of food insecurity was 26%. The adjusted odds of food insecurity were higher among respondents with a disability, from a rural area, and living with dependents. Increasing age, a university education, and income above $80,000/year were protective against food insecurity. Food insecurity more than doubled with a loss of household income above 25% (Adjusted Odds Ratio (AOR): 2.02; 95% CI: 1.11, 3.71; p = 0.022), and the odds further increased with loss of income above 75% (AOR: 7.14; 95% CI: 2.01, 24.83; p = 0.002). Our results suggest that the prevalence of food insecurity may have increased during the COVID-19 pandemic, particularly among economically vulnerable households and people who lost income. Policies that support disadvantaged households and ensure adequate employment opportunities are important to support Australians throughout and post the COVID-19 pandemic.