A restart control device is applied to a vehicle which is provided with an internal combustion engine, an electric motor, a driving wheel, and a clutch. The restart control device has a restart-condition determining portion which determines whether a restart condition for restarting the internal combustion engine is established while the vehicle is coasting; a push-start portion which starts the internal combustion engine by a push-start; a start-up portion which starts the internal combustion engine by use of an electric motor; and a doubly start-up portion which tries to start the internal combustion engine by one of the push-start portion and the start-up portion when the restart-condition determining portion determines that the restart condition is established. The doubly start-up portion tries to start the internal combustion engine by another one of the push-up portion and the start-up portion when the internal combustion engine has not been started.