Nucleation is a fundamental step in crystal growth. Of environmental and materials relevance are reactions that lead to nucleation of iron oxyhydroxides in aqueous solutions. These reactions are difficult to study experimentally due to their rapid kinetics. Here, we used classical molecular dynamics simulations to investigate nucleation of iron hydroxide/oxyhydroxide nanoparticles in aqueous solutions. Results show that in a solution containing ferric ions and hydroxyl groups, iron-hydroxyl molecular clusters form by merging ferric monomers, dimers, and other oligomers, driven by strong affinity of ferric ions to hydroxyls. When deprotonation reactions are not considered in the simulations, these clusters aggregate to form small iron hydroxide nanocrystals with a six-membered ring-like layered structure allomeric to gibbsite. By comparison, in a solution containing iron chloride and sodium hydroxide, the presence of chlorine drives cluster assembly along a different direction to form long molecular chains (rather than rings) composed of Fe-O octahedra linked by edge sharing. Further, in chlorine-free solutions, when deprotonation reactions are considered, the simulations predict ultimate formation of amorphous iron oxyhydroxide nanoparticles with local atomic structure similar to that of ferrihydrite nanoparticles. Overall, our simulation results reveal that nucleation of iron oxyhydroxide nanoparticles proceeds via a cluster aggregation-based nonclassical pathway.