Methods of security negotiation for idle state mobility from a first network to a long term evolution (LTE) network are disclosed. In one embodiment, a service general packet radio service (GPRS) support node (SGSN) of the first network transmits an authentication vector-related key to a mobility management entity (MME). A user equipment (UE) sends its security capabilities including non-access stratum (NAS) security capabilities to the MME. The MME selects a NAS security algorithm, in accordance with the NAS security capabilities of the UE, and sends a message that indicates the selected NAS security algorithm to the UE. The MME also derives, in accordance with the selected NAS security algorithm, a NAS protection key from an authentication vector-related key so as to security communication between the UE and the LTE network.