In recent years, the importance of information security has increased due to the growth in digital communication and steganography has come to the fore for secure communication. Steganography ensures that the secret data to be sent in a multimedia file such as text, picture or video embedded in a way that cannot be understood by third parties. Although image steganography has become popular recently, video steganography has also been widely used and preferred recently, due to its high data hiding capacity and robustness. This paper proposes a new data hiding algorithm in video steganography for effective frame selection, high embedding capacity and good visual quality. The proposed algorithm has two phases: frame selection and data hiding. In the first phase, the frame selection offers a rapid and impressive new method based on enhanced Vigenere. The most significant advantage of this algorithm is to achieve the same level of security without using complex operations such as chaotic systems used in existing methods. In the second phase, we have used adaptive LSB332 for data hiding, which embeds video files with high capacity, high PSNR and SSIM. When the experimental results evaluated, it was observed that the proposed method is over 65 dB PSNR value and 0.99 SSIM value at 20 kbits data capacity. It was also achieved approximately 55 dB and 50 dB PSNR value at 200 kbits and 500 kbits data capacities, respectively, where is no appreciable loss in the SSIM value. Compared to LSB332 based methods, the capacity increased by approximately 12% at same visual qualities. Furthermore, the visual quality of the proposed method is much better than other video data hiding methods, while the capacity increases by 19%.