The dynamic motion of quadrupedal robots on challenging terrain generally requires elaborate spatial–temporal kinodynamic motion planning and accurate control at higher refresh rate in comparison with regular terrain. However, conventional quadrupedal robots usually generate relatively coarse planning and employ motion replanning or reactive strategies to handle terrain irregularities. The resultant complex and computation-intensive controller may lead to nonoptimal motions or the breaking of locomotion rhythm. In this paper, a kinodynamic optimization approach is presented. To generate long-horizon optimal predictions of the kinematic and dynamic behavior of the quadruped robot on challenging terrain, we formulate motion planning as an optimization problem; jointly treat the foot’s locations, contact forces, and torso motions as decision variables; combine smooth motion and minimal energy consumption as the objective function; and explicitly represent feasible foothold region and friction constraints based on terrain information. To track the generated motions accurately and stably, we employ a whole-body controller to compute reference position and velocity commands, which are fed forward to joint controllers of the robot’s legs. We verify the effectiveness of the developed approach through simulation and on a physical quadruped robot testbed. Results show that the quadruped robot can successfully traverse a 30° slope and 43% of nominal leg length high step while maintaining the rhythm of dynamic trot gait.