A method of performing network re-entry of a mobile station based on restart of a base station and an apparatus for performing the same are disclosed. The method comprises the steps of receiving a first message from a base station, the first message including a restart count of which value is varied whenever the base station is restarted; comparing the restart count value with a count value previously stored; and transmitting a second message to the base station if the count values are different from each other, the second message including a first identifier for identifying the mobile station in respect of connection information (context) of the mobile station and a ranging purpose indication field set to a value indicating network re-entry due to restart of the base station.