A vehicle control device is provided. In a structure that engagement of a lock-up clutch and fuel cutoff of an engine are performed during decelerated running of a vehicle, the fuel consumption is saved and torque overload caused by restart of the engine can be prevented. During decelerated running of a vehicle, the lock-up clutch is engaged, the fuel cutoff begins, the lock-up clutch is released when the revolving speed of the engine is lower than the LC-release engine revolving speed threshold and then the fuel cutoff is ended when the revolving speed of the engine is lower than the FC-end engine revolving speed threshold. The LC-release engine revolving speed threshold is increased along with the reduction of the temperature of cooling water of the engine, and the FC-end engine revolving speed threshold is increased along with the reduction of the temperature, so that the increase of the LC-release engine revolving speed threshold is greater than that of the FC-end engine revolving speed threshold. Therefore, the time from the release of the lock-up clutch to the end of the fuel cutoff can be fully guaranteed and the torque overload can be prevented.