In a multimedia communications system (100), a multimedia-based answering system (200) lowers the amount of air interface bandwidth used to send multimedia mail messages. When a called party is unavailable, a user of a user terminal (102) is given an option to send a multimedia mail message for the unavailable called party (300, 302, 304). If the user wants to send a multimedia mail message, the bandwidth requirements for the call are renegotiated to reduce bandwidth for sending the multimedia mail message (306). The multimedia mail message is then transmitted over-the-air to a multimedia mail system (208), where the multimedia mail message is buffered, transcoded (if necessary) and stored until the called party retrieves it (308, 310).