Systems and methods for identifying a motion state of a mobile device are disclosed. In one embodiment, identifying a motion state of a mobile device using acceleration signals from one or more accelerometers comprises: detecting any pedestrial steps associated with a user of the mobile device during an observation period based on the acceleration signals; determining a maximum number of consecutive pedestrial steps taken during the observation period from the detected pedestrial steps; and declaring a high average velocity motion state or a low average velocity motion state for the observation period based on the determined maximum number of consecutive pedestrial steps.