At the time of travel following a travel route, even if an environment around the travel route changes, estimation of a host vehicle position from a stationary object is realized. A vehicle control device has a processor and a memory and controls traveling of a vehicle, and includes a sensor that acquires surrounding environment information of the vehicle, a surrounding environment storage unit that acquires a stationary object from surrounding environment information acquired by the sensor, calculates a position of the stationary object, and stores the position of the vehicle on a travel route and a position of the stationary object in association with each other. The surrounding environment storage unit stores three or more of the stationary objects at each position on a travel route as stationary objects for host vehicle position estimation in a case of receiving a command to start storing the surrounding environment information and the travel route.