A velocity estimation device including an acceleration sensor and a yaw rate sensor is provided. The velocity estimation device determines an initial velocity value of a mobile object based on a velocity estimation expression, an integrated value of acceleration detected by the acceleration sensor, and a relative azimuth calculated from detected yaw rates. The velocity estimation device estimates the velocity of the mobile object based on the initial velocity value and the integrated value of acceleration. In the velocity estimation expression, a magnitude of the velocity vector is constrained by the velocity of the mobile object and a time variation of a direction of the velocity vector is constrained by a time variation of the azimuth of the mobile object in the traveling direction.