Video steganography is a technique that involves hiding secret messages within a video while minimising any noticeable changes or distortions. The proposed work aims to embed multimedia data such as text, image, audio, or video inside a cover video in a secure and inconspicuous manner using different phases such as input preprocessing, frame selection, region selection and data embedding. To enhance the security of input data, the advanced encryption standard (AES) technique was used as a preprocessing step. To embed the encrypted data into the cover video with minimal distortion, key frames were selected using the histogram difference frame selection method. Robust regions were identified from the chosen key frames by applying principal component analysis (PCA) techniques as they offer better resistance to distortions caused by embedding data. Afterwards, the encrypted data was embedded into the robust regions using the adaptive inverted least significant bit-332 technique, which involves the modification of least significant bits of the pixel values. To ensure the receiver could accurately extract embedded information from the video, the indices of the key frames and robust regions were further embedded in random frames generated using a seed function. Experiments were conducted on different cover videos and input datasets to evaluate the performance of the proposed methodology using different quantitative metrics such as Peak signal-to-noise ratio (PSNR), Structural Similarity Index (SSIM), Normalised cross-correlation (NCC) and Bit error rate (BER), pixel embedding capacity and pay load capacity. The results showed that the proposed methodology achieved PSNR values above 60 dB, 50 dB and 40 dB for input data with sizes nearly 100 KB, 1 MB and 10 MB, respectively, and it outperformed the state-of-the-art methods in video steganography with an average pixel embedding capacity of 5.42 bits per pixel and payload embedding capacity of 45.1%.