Methods for implementing an auto-complete feature for contact entry on mobile devices are described. In some embodiments, a mobile device downloads from a server a number of contacts associated with a user, wherein the number of contacts is a subset of contacts in a contact list of the user. Upon receiving a partial contact entry from the user that includes a string of one or more characters, the mobile device identifies contacts from the downloaded contacts matching the partial entry. The mobile device displays no more than a preset number of matching contacts on the display of the mobile device at any one time, in a particular order, with an option for the user to display and fetch for more matching contacts. Other embodiments are also described.