In real-world robotics, motion planning remains to be an open challenge. Not only robotic systems are required to move through unexplored environments, but also their manoeuvrability is constrained by their dynamics and often suffer from uncertainty. One approach to overcome this problem is to incrementally map the surroundings while, simultaneously, planning a safe and feasible path to a desired goal. This is especially critical in underwater environments, where autonomous vehicles must deal with both motion and environment uncertainties. In order to cope with these constraints, this work proposes an uncertainty-based framework for mapping and planning feasible motions online with probabilistic safety-guarantees. The proposed approach deals with the motion, probabilistic safety, and online computation constraints by (i) incrementally representing the environment as a collection of local maps, and (ii) iteratively (re)planning kinodynamically-feasible and probabilistically-safe paths to goal. The proposed framework is evaluated on the Sparus II, a nonholonomic torpedo-shaped AUV, by conducting simulated and real-world trials, thus proving the efficacy of the method and its suitability even for systems with limited on-board computational power.