The traditional locomotion paradigm of quadrupedal robots is to use dexterous (multi-degree-of-freedom) legs and dynamically optimized footholds to balance the body and achieve stable locomotion. However, by looking to nature, tails are widely used as appendages by animals to assist in maneuvering, balancing, manipulating, and propelling. The core advantage of using tails to assist locomotion is that tails can provide a means of influencing the body dynamics independent of the legs’ ground contact. Therefore, using robotic tails to help legged robots to achieve agile locomotion becomes a natural direction of robotics research. With the introduction of a robotic tail, a new quadrupedal locomotion paradigm might be feasible whereby the leg complexity is reduced on the account of incorporating an on-board robotic tail system, especially multi-link tails since they can provide more control inputs. This paper explores this new paradigm by tackling the dynamic locomotion control problem of a reduced complexity quadruped with a robotic tail. For this specific control task, a new control strategy is proposed in a manner that the legs are planned to execute the open loop gait motion in advance, while the tail is controlled in closed loop to affect the quadruped body in the desired orientation. With these two parts working cooperatively, the quadruped can achieve dynamic locomotion. Partial feedback linearization controller is used for the closed loop tail control. Pronking, bounding, and maneuvering are tested to evaluate the controller’s performance. The results validate the proposed controller and demonstrate the feasibility and potential of the new locomotion paradigm.