The simultaneous presence of Fe3+ and As3+ ions in groundwater (higher ppb or lower ppm level concentrations at circumneutral pH) as well as in acid mine drainages (AMDs)/industrial wastewater (up to few thousand ppm concentration at strongly acidic pH) are quite common. Therefore, understanding the chemical interactions prevalent between Fe3+ and As3+ ions in aqueous medium leading to nucleation of ionic clusters/solids, followed by aggregation and growth, is of great environmental significance. In the present work, we attempt to probe the nucleation process of Fe3+-As3+ clusters in solutions of various concentrations and pHs (from AMD to groundwater-like) using a combination of experimental and theoretical techniques. Interestingly, our study reveals nucleation of primary FeAs clusters in nearly all of them independent of concentration or pH. Theoretical studies employed density functional theory (DFT) to predict the primary clusters as stable Fe4As4 units. The surprising resemblance of these clusters with known Fe3+-As3+ minerals at the local level was observed experimentally, which provides an important clue about solid-phase growth from a range of Fe3+-As3+ solutions. Our experimental findings are further supported by a stepwise reaction mechanism established from detailed DFT studies.