For obstacle stepping over of a bio-inspired biped wall climbing robot, a motion planning algorithm based on genetic algorithm is proposed. By analyzing stability requirements and geometrical constraints of obstacle avoidance in Cartesian space, a fitness function is defined with a weighted coefficient method, so that the stability margin and movement cost can attain integrated optimum to a certain extent. By coding its posture in Cartesian space, a collision-free and highly stable motion sequence for the robot is planned, under the constraints in Cartesian space and joint space. Motion planning of the robot stepping over protruding obstacles is implemented in simulation with the proposed algorithm. Results show that the algorithm can guarantee the stability margin of robot motion and the smoothness of the trajectory.