We propose a new algorithm capable of online regeneration of walking gait patterns. The algorithm uses a nonlinear optimization technique to find step parameters that will bring the robot from the present state to a desired state. It modifies online not only the footstep positions, but also the step timing in order to maintain dynamic stability during walking. Inclusion of step time modification extends the robustness against rarely addressed disturbances, such as pushes towards the stance foot. The controller is able to recover dynamic stability regardless of the source of the disturbance (e.g. model inaccuracy, reference tracking error or external disturbance). We describe the robot state estimation and center-of-mass feedback controller necessary to realize stable locomotion on our humanoid platform COMAN. We also present a set of experiments performed on the platform that show the per- formance of the feedback controller and of the gait pattern regenerator. We show how the robot is able to cope with series of pushes, by adjusting step times and positions.