Purpose: NOVA is a food classification system describing a hierarchy from minimally processed to ultra-processed foods (UPF). Research has associated intake of UPF with chronic diseases. In Australia, the primary sources of grains, both refined and whole, are breads and breakfast cereals, which are typically fortified. Most are classified as UPF, yet are recommended core foods according to the Australian Dietary Guidelines (ADG). This research aimed to identify if avoidance of ultra-processed grain foods would alter nutrient intakes in an Australian population and whether sample diets using substitute (non-UPF) foods would be likely to meet nutrient requirements. Methods: Quantitative analysis of usual nutrient intake from the National Nutrition and Physical Activity Survey 2011–12 (n = 12,153) for all foods including and excluding UPF. Dietary modelling examined the nutritional adequacy of sample diets aligned with the ADG and another containing replacements for UPF. We particularly focused on grain foods and meeting whole-grain intake targets. Results: There was a significant decrease (all p < 0.05) in modelled intake of key nutrients when UPF were excluded, specifically, thiamin, folate and iodine, as substitutions are rarely fortified. Diets with no UPF, where substitutes are carefully chosen, have the potential to meet Nutrient Reference Values, but deviation from customary food choices may mean adoption of substitutes is unlikely. Conclusions: Exclusion of UPF may result in lowered intakes of key nutrients of particular concern for at risk groups (including women of child-bearing age), negating gains made by public health policy of fortification. Substitutions may not be realistic in these at-risk populations.