A caller information server provides caller identification (ID) information to a mobile device. The server receives caller ID information from local address books stored on multiple mobile devices. The caller information server aggregates the received caller ID information to generate a pooled address book. The caller information server may determine whether names within the caller ID information are legitimate and store or filter the information accordingly. When a mobile device receives a call from a telephone number for which it lacks caller ID information in its local address book, the mobile device sends a request for the caller ID information for the telephone number, to the caller information server. The server identifies caller ID information associated with the telephone number in the pooled address book, and sends this information to the mobile device.