Hypoxic conditions in waterlogged or flooded soils result in massive penalties to crop production and food security, and the problem is only going to increase under current climate scenarios. While the number of papers dealing with adaptive responses of plants to flooding is increasing exponentially, most staple crops remain highly sensitive to excessive water in the soil. In this work, we analyze the likely reason for this discrepancy. We argue that the current focus on traits aimed to increase the oxygen level in plant tissues under conditions of soil flooding (such as aerenchyma formation, developing adventitious roots, or formation of a radial oxygen loss barrier) is not sufficient to account for all constraints affecting crop performance under stress conditions. By conducting a bioinformatic analysis of a large number of wetland and dryland species, we show that the former species possess a much larger number of gene copies that allow plants to improve acquisition of essential nutrients (such as N and P) as well as to effectively deal with elemental toxicities (e.g. Mn and Fe) originating from changes in redox potential in flooded soils. We then call for a major paradigm shift in our approach to breeding for improved waterlogging stress tolerance by complementing oxygen supply-related traits to those related to vacuolar sequestration of heavy metals and improved nutrient use efficiency. The likely trade-offs of this approach for crop growth under normoxic conditions are discussed. We undertook a comparative bioinformatic analysis between dryland and wetland species, revealing that a larger proportion of gene copies related to nutrient acquisition may contribute to adaptation of wetland plants under hypoxic soil conditions.