Methods and apparatus for facilitating the delivery of e-mail messages from a mobile communication device are disclosed. In one disclosed example, an end user of the mobile device enters e-mail message information corresponding to a new e-mail message through a user interface. Preferably, the user interface is an e-mail graphical user interface (GUI) provided by the mobile device. The mobile device identifies whether a packet data service (e.g. GPRS) for communicating e-mail messages is available to it. If the packet data service is available, the mobile device causes the e-mail message information to be sent via the packet data service. If the packet data service is unavailable, however, the mobile device causes the e-mail message information to be sent in a short message service (SMS) message via an SMS-to-Email service. Advantageously, a common GUI interface which does not change depending on the availability of the packet data service is utilized and service-specific formatting for SMS-to-Email by the end user is not required.