Packet loss is one of the most important factors in degrading Voice over IP (VoIP) perceived call quality. Forward Error Correction (FEC) is a powerful technique for transmitting audio streams over the IP network to decrease the effect of packet loss. Although these method reduces the effect of packet loss, it increases the bandwidth and delay in order to recover from the lost packets. In this paper, we propose a new adaptive FEC mechanism for voice calls based on the generated codewords from a Reed-Solomon (RS) encoder. This mechanism chooses the optimum RS code from a family of codes to improve the conversational call quality. Our proposed mechanism is able to switch between different codes during the call to account for the variation of the network conditions including packet loss and delay. We have deduced the proposed algorithm by performing subjective mean opinion score (MOS) testing based on an interactive assessment tests. We show that our adaptive algorithm outperforms fixed RS codes under highly varying network conditions.