This thesis addresses the problem of generating smooth and efficiently executable locomotion trajectories for legged robots under contact constraints. In addition, we want the trajectories to have the property that small changes in the foot position generate small changes in the joint target path. The first part of this thesis explores methods to select poses for a legged robot that maximises the workspace reachability while maintaining stability and contact constraints. It also explores methods to select configurations based on a reduced-dimensional search of the configuration space. The second part analyses time scaling strategy which tries to minimize the execution time while obeying the velocity and acceleration constraints. These two parts effectively result in smooth feasible trajectories for legged robots. Experiments on the RoboSimian robot demonstrate the effectiveness and scalability of the strategies described for walking and climbing on a rock climbing wall.