Hydrolysis of iron compounds in water leads to the formation of Fe(III) oyxhydroxide-based minerals like ferrihydrite, which act as natural scavengers of inorganic contaminants in the environment. Though studied widely, experimental identification of these oxyhydroxides remains very difficult due to their extreme reactivity. The present study theoretically investigates the formation of Fe(III) oxyhydroxides starting from a single hydrated Fe(III) ion, modeling the formation of larger clusters gradually. The structures, formation enthalpies, and free energies of dimers, trimers, tetramers, and even larger Fe(III) oxyhydroxide clusters comprising of Fe5, Fe7, and Fe13-Keggin ions in gaseous phase and in aqueous medium (using self-consistent reaction field method) are systematically studied using density functional theory. Spontaneous formation of certain multinuclear Fe(III) oxyhydroxide clusters with clear structural signatures of ferrihydrite highlights their potential as prenucleation clusters in the course of mineralization.