Advanced driver assistance systems for heavy duty vehicles, such as lookahead cruise and gearshift controllers, rely on high quality map data. Current digital maps do not offer the required level of road grade information. This contribution presents an algorithm for on-board road grade estimation based on fusion of GPS and vehicle sensor data with measurements from previous runs over the same road segment. An incremental update scheme is utilized to ensure that data storage requirements are independent of the number of measurement runs. Results of the implemented system based on six traversals of a known road with three different vehicles are presented.