We present an algorithm that generates walking motions for quadruped robots without the use of an explicit footstep planner by simultaneously optimizing over both the Center of Mass (CoM) trajectory and the footholds. Feasibility is achieved by imposing stability constraints on the CoM related to the Zero Moment Point and explicitly enforcing kinematic constraints between the footholds and the CoM position. Given a desired goal state, the problem is solved online by a Nonlinear Programming solver to generate the walking motion. Experimental trials show that the algorithm is able to generate walking gaits for multiple steps in milliseconds that can be executed on a real quadruped robot.