To fully utilize the fault-tolerant capability of the X-rudder autonomous undersea vehicles (AUVs), a fault-tolerant motion control algorithm for AUVs oriented towards rudder failures was proposed, and it was deployed on a prototype of an X-rudder AUV. The fault-tolerant motion control algorithm consisted of two parts: dynamics control and control allocation. In dynamics control, the introduction of a multi-loop incremental feedback control algorithm could make the output virtual rudder instruction smooth and gentle. The control allocation algorithm converted the virtual rudder to the control input of the X-rudder actuator by solving a nonlinear programming problem, with the optimization goal of minimizing the allocation error and control output, and the constraints of rudder failure, rudder angle saturation, and other physical limitations were considered. This also enabled the X-rudder AUV to have fault-tolerant motion capabilities. Field trial results show that the rudder instructions generated by the fault-tolerant motion control algorithm proposed in this paper are smooth, and the X-rudder AUV still maintains a certain navigation control capability after the rudder failure. This has a certain guiding significance for the design of a fault-tolerant steering system applied to X-rudder AUVs.