Methods and apparatus for efficiently managing the storage of e-mail message information for a mobile station are described. In one illustrative example, a plurality of e-mail messages are received by the mobile station through a wireless network and stored in memory. If a size of the e-mail messages reaches a predetermined limit of the memory, e-mail message bodies of some of the e-mail messages (e.g. relatively “old” e-mails) are automatically deleted from the memory while e-mail message headers of the e-mail messages are retained. E-mail message headers of e-mail messages having deleted e-mail message bodies may still be visually displayed in a list at the mobile station. Subsequently, if a user selection of one of these e-mail messages in the list is identified, an e-mail message body of the e-mail message is requested by the mobile station and received from a server through the wireless network. Thus, the e-mail message body of the selected e-mail message may still be visually displayed at the mobile station.