Unified messaging brings together the various communication services including e-mail, fax, voice and video messages into one single mechanism for transportation over the Internet. This helps reduce costs by circumventing expensive international toll charges and eliminates the need for multiple communication devices for sending and receiving different types of media data. In the age of mobile communication, there is a growing demand for wireless messaging support for mobile users. However, wireless links are typically low bandwidth, costly and unreliable. Although most of the existing messaging systems can be extended to support wireless messaging via wireless network, they are unable to operate efficiently over the wireless environment. This paper proposes a number of techniques such as compression, on-demand retrieval, multi-part retrieval, content summarization and attachment conversion to support wireless messaging. These techniques have been incorporated into the Wireless Messaging Gateway System (WMGS) which supports e-mail, fax, voice mail, paging and short messaging services for the integrated Internet and wireless environment. Performance results have shown that significant savings on bandwidth utilization and transmission time have been achieved.