A scheme for message folder synchronization. In one embodiment, a method may comprise: automatically detecting arrival of a message at a messaging server for a user; storing the message in a first folder of a first folder system associated with the user at the messaging server; processing at least a portion of an instance of the message for transmission to the user's mobile data communication device over a wireless network; receiving a status signal from the mobile data communication device indicating that the message has been moved from a first folder at the mobile data communication device to a second folder of a second folder system associated with the user at the mobile data communication device; and responsive to the status signal, moving the message from the first folder of the first folder system at the messaging server to a second folder thereat corresponding to the second folder of the second folder system.