An apparatus, system, and method provide voicemail service using a packet data messaging service such as multimedia message service (MMS). Upon detecting that the presence status of a destination device is “unavailable”, the voicemail message is recorded at an origination mobile station and transmitted in a packet data message through a packet data messaging service center such as a multimedia messaging service center (MMS-C). If the destination device is a destination mobile station subscribing to the packet data messaging service, the packet data message is deposited in the destination mobile station.