Distance travelled is a crucial metric that underpins an animal's ability to navigate in the short-range. While there is extensive research on how terrestrial animals measure travel distance, it is unknown how animals navigating in aquatic environments estimate this metric. A common method used by land animals is to measure optic flow, where the speed of self-induced visual motion is integrated over the course of a journey. Whether freely-swimming aquatic animals also measure distance relative to a visual frame of reference is unclear. Using the marine fish Rhinecanthus aculeatus, we show that teleost fish can use visual motion information to estimate distance travelled. However, the underlying mechanism differs fundamentally from previously studied terrestrial animals. Humans and terrestrial invertebrates measure the total angular motion of visual features for odometry, a mechanism which does not vary with visual density. In contrast, the visual odometer used by Rhinecanthus acuelatus is strongly dependent on the visual density of the environment. Odometry in fish may therefore be mediated by a movement detection mechanism akin to the system underlying the optomotor response, a separate motion-detection mechanism used by both vertebrates and invertebrates for course and gaze stabilisation.