A travel resistance arithmetic device includes: a controller configured to estimate travel resistance which a vehicle receives from a travel road; and a memory configured to store the travel resistance in association with positional information. The controller is configured to: correct, based on difference between a stored value of the travel resistance stored in the memory in association with a predetermined area on the travel road through which the vehicle has already passed and an estimated value of the travel resistance estimated by the controller in the predetermined area, the stored value stored in the memory in association with a correction target area on the travel road and; output the corrected stored value as the travel resistance in the correction target area while the vehicle travels the travel road.