Systems and methods that provide NAS security protection for mobile networks. In one embodiment, a network element of a mobile network performs a NAS procedure in multiple phases to establish a NAS communication session with User Equipment (UE) when no NAS security context exists. For a first phase, the network element receives an initial NAS message from the UE populated with a subset of NAS protocol Information Elements (IEs) designated for security-related handling, selects a NAS security algorithm for the NAS security context, and sends a response to the UE that indicates the NAS security algorithm. For a second phase, the network element receives a subsequent NAS message from the UE having a NAS message container that contains the initial NAS message populated with each of the NAS protocol IEs for the NAS procedure, and decrypts the NAS message container of the subsequent NAS message using the NAS security algorithm.