A vehicle control device disengages a clutch provided between an engine and a driving wheel at a brake-off and an accelerator-off during traveling of the vehicle, and stops the engine and carries out inertia traveling. The vehicle control device starts the engine by the push-start by engaging the clutch and by transmitting the power of the driving wheel to the engine, if it is determined that a brake pedal has been depressed during the inertia traveling.