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 the signaling problems occurring between the UE and the MME in a situation where it is necessary for a network node to identify the UE and acquire UE information, if there is any, from another network node to which the UE has been attached, are provided. The method for communication between the UE and network based on the NAS protocol messages and operations is implemented with the involvement a UE, an MME, and an old MME or an old Serving General Packet Radio Service (GPRS) 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 the 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.