This paper proposes a new algorithm for hiding data in the frequency domain of digital images using the discrete cosine transform. This algorithm uses quantization index modulation (QIM) as the basic embedding operation. Frequency embedding is characterized by the problem of error appearance in a secret message arising directly at the embedding stage. The embedded message is distorted due to the loss of information when restoring integer pixel values from the frequency domain. This problem is significant if the integrity of the transmitted information is critical. For example, an insignificant distortion of an encrypted message leads to the impossibility of decrypting and, consequently, to the loss of all encrypted information. The proposed algorithm solves this problem via an iterative embedding procedure, which corrects the arising errors. Another distinctive feature of this algorithm is the adaptive correction of distortions of the frequency coefficients’ histogram. For this purpose, the embedding procedure adapts to the features of the image and masks the arising distortions. Computing experiments and comparison with the state-of-the-art demonstrate the effectiveness of our algorithm.