This paper treats the problem of estimating the longitudinal velocity of a braking vehicle using measurements from an accelerometer and wheel speed data from standard anti-lock braking wheel speed sensors. We develop and experimentally test three velocity estimation algorithms of increasing complexity. The algorithm that works the best gives peak errors of less than 3 percent even when the accelerometer signal is significantly biased.