Many effective methods of the data embedding into digital images are based on the frequency transformations. However use of similar transformations is connected to the following problem: the built-in message is distorted because of information losses in case of restoration of pixels’ integer values from the frequency domain. It represents a vital issue if the integrity of the transmitted data is critical. For example, an insignificant distortion of the ciphered message results in impossibility of deciphering and to loss of all ciphered information. In this paper is described the new algorithm of the information embedding into digital images on the basis of the discrete Fourier transformation allowing to provide unmistakable extraction of the built-in messages from the frequency domain. The faultlessness is reached through an iterative procedure of embedding and non-uniform distribution of the message parts for the image-container’s blocks. Our algorithm not only solves a problem of the built-in messages distortions, but also provides high visual quality of stego-image. Moreover, our approach to the unmistakable embedding of information into the digital images frequency domain is applicable not only for the discrete Fourier transformation, but also for other frequency transformations.