Method for leaving a voice message, by an audio terminal (T_A) belonging to a user wishing to leave a voice message for the attention of another user, with a voice messaging server to which the other user is subscribed and comprising at least two audio coders (CO1, CO2) which operate respectively in first and second predetermined frequency bands, the first frequency band being wider than the second frequency band and containing the latter, said method being characterized in that it comprises, at the level of the voice messaging server, the steps consisting in: - determining (S1-S6b), prior to the leaving of the voice message, whether an audio terminal (T_B) belonging to the user subscribed to the voice messaging server normally uses at least one audio coder operating in the first predetermined frequency band or at least one audio coder operating in the second predetermined frequency band, - identifying, during the leaving of the voice message by the audio terminal of the user wishing to leave said voice message, the audio coders liable to be used by the audio terminal of the user wishing to leave said voice message, - if at least two identified audio coders operate respectively in the first and second predetermined frequency bands, • selecting (SE3a) from the audio terminal of the user wishing to leave the voice message, the audio coder operating in the first predetermined frequency band, if the voice messaging server has previously determined that the audio terminal belonging to the subscribed user normally uses an audio coder operating in the first predetermined frequency band, • selecting (SE3b or SE4) from the audio terminal of the user wishing to leave the voice message, the audio coder operating in the second frequency band if the voice messaging server has previously determined that the audio terminal belonging to the subscribed user normally uses an audio coder operating in the second predetermined frequency band, - recording the voice message left, in the coding format in accordance with the audio coder which has been selected from the audio terminal of the user wishing to leave the voice message. - determining (S1-S6b), prior to the leaving of the voice message, whether an audio terminal (T_B) belonging to the user subscribed to the voice messaging server normally uses at least one audio coder operating in the first predetermined frequency band or at least one audio coder operating in the second predetermined frequency band, - identifying, during the leaving of the voice message by the audio terminal of the user wishing to leave said voice message, the audio coders liable to be used by the audio terminal of the user wishing to leave said voice message, - if at least two identified audio coders operate respectively in the first and second predetermined frequency bands, • selecting (SE3a) from the audio terminal of the user wishing to leave the voice message, the audio coder operating in the first predetermined frequency band, if the voice messaging server has previously determined that the audio terminal belonging to the subscribed user normally uses an audio coder operating in the first predetermined frequency band, • selecting (SE3b or SE4) from the audio terminal of the user wishing to leave the voice message, the audio coder operating in the second frequency band if the voice messaging server has previously determined that the audio terminal belonging to the subscribed user normally uses an audio coder operating in the second predetermined frequency band, • selecting (SE3a) from the audio terminal of the user wishing to leave the voice message, the audio coder operating in the first predetermined frequency band, if the voice messaging server has previously determined that the audio terminal belonging to the subscribed user normally uses an audio coder operating in the first predetermined frequency band, • selecting (SE3b or SE4) from the audio terminal of the user wishing to leave the voice message, the audio coder operating in the second frequency band if the voice messaging server has previously determined that the audio terminal belonging to the subscribed user normally uses an audio coder operating in the second predetermined frequency band, - recording the voice message left, in the coding format in accordance with the audio coder which has been selected from the audio terminal of the user wishing to leave the voice message.