Spherical Fe-oxide concretions on Earth, especially in Utah, USA, have been investigated as an analog of hematite spherules found in Meridiani Planum on Mars to support interpretations of water-rock interactions in early Mars. Although several formation mechanisms have been proposed for the Fe-oxide concretions on Earth, it is still unclear whether these mechanisms are viable because a precise formation process and precursor of the concretions are missing. This paper presents evidence that Fe-oxide concretions in Utah and newly found Fe-oxide concretions in Mongolia had spherical calcite concretions as precursors. Different formation stages of calcite and Fe-oxide concretions observed, both in Utah and Mongolia, indicate that calcite concretions initially formed within eolian sandstone strata and were dissolved by infiltrating Fe-rich acidic waters to form spherical FeO(OH) crusts due to pH buffering. The similarity between these Fe-oxide concretions on Earth and the hematite spherule occurrences in Meridiani Planum, combined with evidence of acid sulfate water influences on Mars, suggest that the hematite spherules also formed from dissolution of preexisting carbonate spherules possibly formed under a dense carbon dioxide early martian atmosphere.