A method is provided for managing mobility of an Access Terminal (AT) in a mobile communication system using a Mobile Internet Protocol (MIP). The method includes generating, by an AT that has entered a new network, a Security Parameter Index (SPI) and a security key for mutual authentication with a Home Agent (HA) of the new network, sending, by the AT, a registration request message including authentication information including the SPI, the authentication information being generated using the security key, upon receipt of the registration request message, searching, by the HA, a database for the SPI included in the authentication information, verifying the authentication information according to the search result, upon successful verification of the authentication information, generating, by the HA, mobility binding information of the AT, and sending, by the HA, a registration response message including the HA's IP address.