Understanding the semiconductor-electrolyte interface in photoelectrochemical (PEC) systems is crucial for optimizing the stability and reactivity. Despite the challenges in establishing reliable surface structure models during PEC cycles, this study explores the complex surface reconstructions of BiVO4(010) by employing a computational workflow integrated with a state-of-the-art active learning protocol for a machine-learning interatomic potential and global optimization techniques. Within this workflow, we identified 494 unique reconstructed surface structures that surpass conventional chemical intuition-driven, bulk-truncated models. After constructing the surface Pourbaix diagram under Bi- and V-rich electrolyte conditions using density functional theory and hybrid functional calculations, we proposed structural models for the experimentally observed Bi-rich BiVO4 surfaces. By performing hybrid functional molecular dynamics simulations with the explicit treatment of water molecules on selected reconstructed BiVO4(010) surfaces, we observed water dissociation from molecular water. Our findings demonstrate significant water dissociation on reconstructed Bi-rich surfaces, highlighting the critical role of bare and undercoordinated Bi sites (only observable in reconstructed surfaces) in driving hydration processes. Our work establishes a foundation for understanding the role of complex, reconstructed Bi surfaces in surface hydration and reactivity. Additionally, our theoretical framework for exploring surface structures and predicting reactivity in multicomponent oxides offers a precise approach to describing complex surface and interface processes in PEC systems.