Video Steganography is a method for securing data in a video file and hence it prevents the chance of theft. The proposed scheme uses the Video Steganography technique on the encrypted data (using RSA and AES) for providing maximum security and stability. In this work, a secured Video Steganographic scheme is proposed using Sudoku puzzle. The novelties of the work imply that nobody could be able to see as well as modify data during transmission as the secret message is first encrypted into cipher text twice using RSA and AES cryptographic technique then that cipher text is embedded in video using a Sudoku reference matrix. So, our proposed work combines both Cryptographic and Steganographic technique to enhance the security in maximum level with maintained computational complexity. © 2018, Springer Nature Singapore Pte Ltd.