Convective weather and its inherent uncertainty constitute one of the major challenges in the air traffic management (ATM) system, entailing both safety hazards and economic losses. In the present work, we propose a stochastic algorithm for trajectory planning that ensures feasibility and safety of the path between two points while avoiding unsafe stormy regions. The uncertain zone to be flown is described by an ensemble of equally likely forecasts. We design a scenario-based optimal rapidly exploring random tree (SB-RRT*), and we able to dynamically allocate risk during its expansion so that a safety margin is not violated. The solution is a safe continuous trajectory that minimizes the distance covered. We present preliminary results assuming weather to be the only source of uncertainty. We consider an aircraft point-mass model at constant altitude and airspeed with manoeuvres being limited by a minimum turning radius. © 2021, Springer Nature Singapore Pte Ltd.