Step detection is very important for the foot-mounted Pedestrian Dead Reckoning (PDR) system. To deal with the false detection caused by variant stepping modes and occasional disturbance, a novel robust step detection algorithm is proposed. The proposed algorithm detects the number of steps and zero-velocity phase using data from inertial sensors mounted on the user’s foot. It includes two parts: a novel anti-fault detection algorithm and a novel zero-velocity detection method, which are used to reduce the over-detection and miss-detection of steps, respectively. Field tests show that the proposed approach is robust under varying motion speeds in different step modes for different persons and the average accuracy of the proposed algorithm is 99.94% in all motion modes, which significantly exceeds conventional estimation approaches in terms of step detection accuracy.