This application discloses a method for establishing a call connection, a first terminal, a server, and a storage medium. The method includes: obtaining, by a first terminal, a second vocoder list of a second terminal, the second vocoder list including vocoders supported by the second terminal and with corresponding priorities; determining, by the first terminal, a first vocoder with the highest priority among vocoders that exist in both a first vocoder list of the first terminal and the second vocoder list, the first vocoder list including vocoders supported by the first terminal and with corresponding priorities, and the priorities of the vocoders being positively correlated with audio frequencies in encoding and decoding of the vocoders; and requesting, by the first terminal by using the first vocoder, to establish a first call connection to the second terminal.