A system and a method for performing session setup in a wireless communication system that uses a Mobile Internet Protocol (MIP) are provided. In the method, when at least one Mobile Node (MN) requests registration, a Network Access Identifier (NAI) of the MN is determined. A session Identification (ID) is assigned to the NAI of the MN. The session ID assigned to the NAI is inserted into an Identification Low field forming a registration request field of a message requesting registration of the MN. The message is transmitted to a Home Agent (HA) of the MN. A Foreign Agent (FA) can more easily search for an MN corresponding to a registration reply message provided from the HA, and memory consumption and a time delay that occurs due to a hash method may be reduced.