Iron-rich carbonates and the oxidized remains of former carbonates (iron-oxide concretions) underlie bleached Navajo Sandstone over large portions of southern Utah. Iron in the carbonates came from hematite rims on sand grains in the upper Navajo that were dissolved when small quantities of methane accumulated beneath the sealing Carmel Formation. As a second buoyant gas (CO2 derived from Oligocene–Miocene magmas) reached the seal and migrated up dip, it dissolved in the underlying water, enhancing the solution’s density. This water carried the released ferrous iron and the methane downward. Carbonates precipitated when the descending, reducing water degassed along fractures. The distribution of a broad array of iron-rich features made recognition of the extent of the ancient flow systems possible. Although siderite is not preserved, dense, rhombic, mm-scale, iron-oxide pseudomorphs after ferrous carbonates are common. Distinctive patterns of iron oxide were also produced when large (cm-scale), poikilotopic carbonate crystals with multiple iron-rich zones dissolved in oxidizing waters. Rhombic pseudomorphs are found in the central cores of small spheroids and large (meter-scale), irregular concretions that are defined by thick, tightly cemented rinds of iron-oxide–cemented sandstone. The internal structure and distribution of these features reveal their origins as iron-carbonate concretions that formed within a large-scale flow system that was altered dramatically during Neogene uplift of the Colorado Plateau. With rise of the Plateau, the iron-carbonate concretions passed upward from reducing formation water to shallow, oxidizing groundwater flowing parallel to modern drainages. Finally they passed into the vadose zone. Absolute dating of different portions of these widespread concretions could thus reveal uplift rates for a large portion of the Plateau. Iron-rich masses in other sedimentary rocks may reveal flow systems with similar histories.