A movement distance estimating device includes: a memory; and a processor coupled to the memory and configured to: determine, based on a first image and a second image included in images captured by an image capture device mounted on a moving body, an amount of relative movement of the moving body between a first time point at which the first image is captured and a second time point at which the second image is captured, determine a scale for the amount of relative movement, based on a relation in a three-dimensional space between a road surface and a spatial point corresponding to a feature point in an area other than a road-surface area in at least one image of the captured images, and determine a movement distance of the moving body between the first and second time points, based on the amount of relative movement and the scale.