As the penetration of renewable distributed generation (RDG) continues to grow, the stochastic and intermittent nature of its output imposes significant challenges on distribution networks (DNs), such as source–load mismatch and voltage fluctuations, which seriously affects the safety and reliability of the system. Thus, this paper presents a stochastic optimal allocation method for a battery energy storage system (BESS) in the DN, with the consideration of annual load growth, BESS degradation, and DN operation, aiming to minimize the overall cost of DNs and harvest more renewable energy. Based on the rainflow-counting concept, BESS degradation is efficiently modeled and linearized to improve solvability. Additionally, to address the uncertainties of RDG outputs and loads, a stochastic optimization (SO) method is adopted. Furthermore, considering that a large number of integer variables of the BESS allocation model may cause a heavy computational burden, a feasibility pump-based solution algorithm is introduced to accelerate the solving speed. Finally, the effectiveness of the proposed BESS allocation method and the solution algorithm is verified on a 33-bus DN system through comparative analyses, showing high efficiency and performance.