In this paper, we present the mathematical design and implementation of a fault-tolerant control scheme for a bio-inspired underwater robot with four flexible fins. The proposed active fault-tolerant control scheme re-configures the force allocation matrix using the Elimination of Column Method, depending on which fin actuator is faulty. The proposed method allows to decouple the 6-DOF controllable underwater vehicle using the remaining three fins. The efficacy of the proposed method is assessed experimentally for trajectory tracking of an ellipsoidal-shaped trajectory using two different controllers, namely PID control and Sliding Mode control. The obtained results show that the combination of a sliding mode controller with the proposed fault-tolerant control allocation approach ensures an efficient trajectory tracking control performance when faults occur.