A mobile device for synchronizing contact data stores comprising: a host having: a database for storing contact records; and a contact application communicating with the database and being capable of altering the contact records; a client having: a client contact application capable of altering the contact records; and a client data manager communicating with the client contact application for storing contact records; a state machine; a client listener to determine when a change has been made and propagate the change to the host; and a host listener to determine when a client record has been changed in the database and propagate the change to the client, wherein the database and the client data manager are synchronized through the state machine. Also, a method for synchronizing contact record storage by notification and propagation of changes through the state machine upon changes occurring in the database and client data manager.