An audio message service apparatus comprises a first memory to store an encoded audio message, a second memory to store management data regarding the encoded audio message stored in the first memory and an encoder for again encoding the encoded audio message stored in the first memory by another different encoding method on the basis of the management data stored in the second memory and for storing the audio message which was again encoded into the first memory. The encoder encodes the encoded audio message by an encoding method of a higher compression ratio.