A vehicle control device includes an engine that is a power source of a vehicle, a transmission configured to connect the engine to a drive wheel of the vehicle, and a clutch configured to connect or block transmission of power between the engine and the drive wheel through the transmission. The vehicle control device is capable of executing predetermined control to allow the vehicle to travel while stopping supplying fuel to the engine and releasing the clutch that has been engaged, during travel of the vehicle, and the vehicle control device downshifts the transmission at the time the clutch is released in the predetermined control. It is possible to shift the transmission into a lowest-speed side gear ratio by the downshift.