A method and apparatus for efficient paging of user equipment (UE) in an LTE network is disclosed. In addition to storing the Last Seen eNodeB (LSeNB) for each UE attached to a mobility management entity (MME), the MME also maintains an LSeNB List of the eNodeBs seen immediately before the LSeNB for each UE. When a notification for a UE arrives at the MME, then MME can select from several paging methods, including paging only the LSeNB to locate the UE and sending a paging request LSeNB as well as to the list of eNodeBs seem immediately before the LSeNB. The MME can send a paging request to more than a single eNodeB but less than a full Tracking Area. Efficient paging is especially needed for voice over internet protocol (VoIP) calls where a call will go to voice mail if a page isn't answered quickly.