A method and apparatus for supporting Non-Access Stratum (NAS) communication between a User Equipment (UE) and a Mobility Management Entity (MME) efficiently by addressing signaling problems occurring between the UE and the MME in a situation where it is necessary for a network node to identify the UE information, from another network node to which the UE has been attached, are provided. The method is implemented with a UE, an MME, and an old MME or an old Serving General Packet Radio Service Support Node (SGSN) to which the UE has been attached before so as to facilitate discovering a best node using the UE information acquired from the old MME or old SGSN during communication between the UE and the network, resulting in a reduction of a communication delay between the UE and network and an improvement of communication efficiency.