We propose a novel state estimator for legged robots, STEP, achieved through a novel preintegrated foot velocity factor. In the preintegrated foot velocity factor, the usual non-slip assumption is not adopted. Instead, the end effector velocity becomes observable by exploiting the body speed obtained from a stereo camera. In other words, the preintegrated end effector's pose can be estimated. Another advantage of our approach is that it eliminates the necessity for a contact detection step, unlike the typical approaches. The proposed method has also been validated in harsh-environment simulations and real-world experiments containing uneven or slippery terrains.