Hybrid Electric Vehicles (HEVs) enable fuel savings by re-using kinetic and potential energy that was recovered and stored in a battery during braking or driving down hill. Besides, the vehicle itself can be seen as a storage device, where kinetic energy can be stored and retrieved by changing the forward velocity. It is beneficial for fuel consumption to optimize the velocity trajectory in two ways; i) to assist the driver in tracking an optimal velocity trajectory (e.g. input to an Adaptive Cruise Controller); ii) to estimate the future power request trajectory which can be used to optimize the hybrid components use. Taking advantage of satellite navigation, together with the vehicles current mass and road load parameters, an optimization problem is formulated, and solved for a driver defined time constraint. Despite tight velocity constraints, this can result in 5% fuel saving compared to a Cruise Controller with constant velocity setpoint. The benefit of velocity trajectory optimization is indicated with experimental results. © 2010 AACC.