A mobile communication terminal, a mobile switching center, a storage device, and a message storing method are provided, whereby a high-quality message is allowed to store in an efficient manner. A network system, when discriminating that a receiving-side terminal cannot answer a call made from a calling-side via a communication line of a circuit-switched network, the communication line with the calling-side terminal is switched from the circuit-switched network to a packet-switched network. The network system stores in the storage device the message that has been transmitted via the communication line of the packet-switched network that has been switched without performing a Codec conversion. The network system performs a Codec conversion of the message to an optimal one, and then delivers the message to the receiving-side terminal.