Image steganography and watermarking have demonstrated their efficiency in creating a covert communication channel and in digital image authentication respectively. The importance of cybersecurity tasks sets high efficiency requirements for information embedding methods. Many studies in this area focus on finding new ways to improve the embedding quality. One of them is to use metaheuristic optimization algorithms. The use of classical metaheuristics is common enough for a data hiding area. However, a lot of new metaheuristics have been proposed over the past few years. Their applicability has not yet been evaluated in the field of steganography and digital watermarking. In this paper, we present a comparative study on the efficiency of seven metaheuristic optimization algorithms for finding the best embedding options in the phase spectrum of the Discrete Fourier Transform (DFT). One of the contributions of our research is an improved DFT-based data hiding algorithm, which is a development of the error-free embedding algorithm we obtained earlier. The new algorithm also provides error-free extraction of embedded data, and it is distinguished by the high invisibility of embedding through the use of metaheuristic optimization. The use of metaheuristic optimization led to an increase in the PSNR value by an average of 2%–6% and an increase in the capacity value by an average of 16%–25%. Another important contribution of our research is the original formulation of the optimization problem for different classes of metaheuristics. The experimental results demonstrate the efficiency of metaheuristic optimization for solving data hiding problem. The Differential Evolution and the Particle Swarm Optimization showed the best values of embedding indicators among the classical metaheuristic optimization algorithms. The Gradient-Based Optimizer showed the highest efficiency among modern algorithms. Thus, our research indicates the relevance of further studies of other modern optimization algorithms for a data hiding area.