A vehicle speed estimator includes a unit that selects a minimum rotation speed among rotation speeds of wheels detected by a rotation speed detector and calculates a reference wheel speed of a construction vehicle at every predetermined time. The unit includes: a variable filter processor that performs a low-pass filter processing to the minimum rotation speed, the variable filter processor having a variable time constant; and a time constant changer that changes the time constant of the variable filter processor in accordance with travel conditions of the construction vehicle.