A location registration method of a terminal in a mobile communication system is provided. The method transmitting a location registration request message to a network, waiting, when a reject message is received from the network in response to the location registration request message, until a radio connection with the network releases completely, and transmitting, when the radio connection is released, a new location registration request message to the network.