A new unified motion planning algorithm for autonomous Underwater Vehicle-Manipulator Systems (UVMS) has been presented in this paper. Commonly, a UVMS consists of two sub-systems, a vehicle and a manipulator, having vastly different dynamic responses. The proposed algorithm considers the variability in dynamic bandwidth of the complex UVMS system and generates not only kinematically admissible but also dynamically feasible reference trajectories. Additionally, this motion planning algorithm exploits the inherent kinematic redundancy of the whole system and provides reference trajectories that accommodates other important criteria such as thruster/actuator faults and saturations, and also minimizes hydrodynamic drag. Effectiveness of the proposed unified motion planning algorithm has been verified by extensive computer simulation. The results are quite promising.