An idle-stop operation control device that performs an idle-stop operation on an internal combustion engine of a vehicle, comprising: a programmable controller that is activated by an ignition switch of the vehicle using a power supplied from a battery mounted on the vehicle and performs an idle-stop operation control routine repeatedly such that an operation of the internal combustion engine is ceased in an idle operation state and an engine start-up operation is performed on the internal combustion engine from an operation-ceased state upon request by operating a starter motor using a power of the battery ; and a sensor that detects a terminal voltage of the battery ; characterized in that said controller is programmed to: determine if the present occasion corresponds to an occasion immediately after the controller is activated (S1); determine that the controller has experienced an unexpected restart in the course of the engine start-up operation when the present occasion is determined to correspond to the occasion immediately after the controller is activated and the terminal voltage of the battery is lower than a restart determining value (VA)(S2); and prevent the idle-stop operation from being executed on the internal combustion engine if it is determined that the controller has experienced the unexpected restart in the course of the engine start-up operation (S4), while performing the idle-stop operation on the internal combustion engine in other case. a programmable controller that is activated by an ignition switch of the vehicle using a power supplied from a battery mounted on the vehicle and performs an idle-stop operation control routine repeatedly such that an operation of the internal combustion engine is ceased in an idle operation state and an engine start-up operation is performed on the internal combustion engine from an operation-ceased state upon request by operating a starter motor using a power of the battery ; and a sensor that detects a terminal voltage of the battery ; characterized in that said controller is programmed to: determine if the present occasion corresponds to an occasion immediately after the controller is activated (S1); determine that the controller has experienced an unexpected restart in the course of the engine start-up operation when the present occasion is determined to correspond to the occasion immediately after the controller is activated and the terminal voltage of the battery is lower than a restart determining value (VA)(S2); and prevent the idle-stop operation from being executed on the internal combustion engine if it is determined that the controller has experienced the unexpected restart in the course of the engine start-up operation (S4), while performing the idle-stop operation on the internal combustion engine in other case. determine if the present occasion corresponds to an occasion immediately after the controller is activated (S1); determine that the controller has experienced an unexpected restart in the course of the engine start-up operation when the present occasion is determined to correspond to the occasion immediately after the controller is activated and the terminal voltage of the battery is lower than a restart determining value (VA)(S2); and prevent the idle-stop operation from being executed on the internal combustion engine if it is determined that the controller has experienced the unexpected restart in the course of the engine start-up operation (S4), while performing the idle-stop operation on the internal combustion engine in other case. <EOS>