A method of supporting Voice over Internet Protocol (VOIP) media codecs on a voice processing system stores voice response segments in each of a plurality network native formats. Each of the network native formats corresponds to a media codec. The method receives a call from a caller over an IP network. The method determines a negotiated codec for the call. If the call requires a required voice response segment, the method retrieves the required voice segment in the network native format corresponding to the negotiated codec. The method then sends the required voice segment in the network native format corresponding to the negotiated codec to the caller over IP network. If the call includes a voice message from the caller, the method stores the voice message from the caller in the network native format corresponding to the negotiated codec. If the call requires retrieval of a voice mail message for the caller, the method retrieves the voice mail message. If the voice mail message is in the network native format corresponding to the negotiated codec, the method sends the voice mail message in the network native format corresponding to the negotiated codec to the caller over the IP network. If the voice mail message is not in the network native format corresponding to the negotiated codec, the method converts the voice mail message into the network native format corresponding to the negotiated codec, and sends the converted voice mail message in the network native format corresponding to the negotiated codec to the caller over the IP network.