An electronic navigation device for a human user may include a housing to be carried by the human user, and at least one accelerometer carried by the housing and configured to sense acceleration during motion of the human user. The electronic navigation device may also include a controller carried by the housing and coupled to the at least one accelerometer. The controller may be configured to generate a plurality of acceleration sample values as the human user moves over a given distance, and determine an estimated distance traveled by the human user during movement over the given distance by at least multiplying each acceleration sample value by a scaling constant. The controller may also be configured to sum results thereof.