Systems and methods for wirelessly provisioning a mobile communication device are provided. To provision the mobile communication device to operate with an electronic messaging system, a provisioning request message may be generated at the mobile communication device. The provisioning request message may include a wireless identification for identifying the mobile communication device in a wireless network. The provisioning request message may be transmitted from the mobile communication device to the electronic messaging system using a pre-established communication link. In response to detecting the provisioning request message, the electronic messaging system may be provisioned by storing the wireless identification for use in communicating with the mobile communication device.