A method of planning crab gaits for a quadruped walking robot is proposed. In the conventional gait study, one of the major concerns has been the foothold selection based on a prescribed body motion, but, in the paper, we consider the body motion planning problem under the assumption that a set of irregular footholds is given, and propose a hierarchical strategy. The strategy can be divided into three stages: first, a feasible range of the body movement is sought under the kinematic limit and the stability constraint. Next, a swing-leg sequence is selected with the aid of a proposed measure of traversability. Finally, an optimal sequence of the body motion is planned by the proposed procedure of otpimizing the gait stability margin. To verify the efficiency of the proposed method, simulation results are presented.