Estimating vehicle velocity in the full-range of vehicle operation across various driving scenarios is a challenge for most model-based state observers, especially for vehicles operating at the limits of handling due to highly nonlinear vehicle dynamics, particularly on slippery roads. To address this challenge, this paper proposes a machine learning (ML) based method for vehicle velocity estimation.  Two novel vehicle velocity estimators based on multi-layer feedforward neural network (FNN) are designed to estimate vehicle longitudinal and lateral velocities, respectively. The inputs of the proposed FNN estimators are selected based on a sensitivity analysis of vehicle dynamics models and are normalized by vehicle parameters to ensure that the trained FNN estimators have generic formulas transferable to vehicles of different specifications. Experimental and simulation results—including tests on vehicles not seen during training—demonstrate that the proposed velocity estimators provide accurate estimations in various challenging scenarios and are robust to differences in vehicle specifications.  Moreover, the computational cost is low enough for real-time implementation.